21

One major application of topology in semantics is the topological approach to computability. The basic idea of the topology of computability comes from the observation that termination and nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it ...


9

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of $n$ points $(x_i,y_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes ...


8

The best published results all appear in a 1997 paper by Jianer Chen, Saroja P. Kanchi, and Arkady Kanevsky. For any fixed $\varepsilon>0$, computing the genus of a graph with additive error $O(n^\varepsilon)$ is NP-hard. There is a trivial linear-time algorithm to embed any $n$-vertex graph of (unknown) genus $g$ on an orientable surface of genus $\max\{...


7

The problem is $\mathsf{NP}$-hard. See [GT41] DIRECTED BANDWIDTH in Garey and Johnson.


6

Since you only care about embeddings in the plane, and every oriented homeomorphism of the plane is isotopic to the identity (Alexander's trick), testing whether two embedded graphs are isotopic is equivalent to testing whether they are congruent by an oriented homeomorphism. And this is a purely combinatorial notion: for example it is equivalent to the two ...


5

I wanted to add to JɛffE's comprehensive answer that to the best of my knowledge there are no lower bounds on the approximation factor for this problem. As far as we know, there can be an approximation algorithm that always gives a constant factor approximation (even if the genus is very small). The paper Chen, Kanchi, and Kanevsky [CKK '97] only says that ...


4

A combinatorial embedding or signed rotation system is a combinatorial representation of a cellular embedding of a graph on some surface. An embedding is a drawing of the graph such that no two edges cross; an embedding is cellular if every face is a disk. Consider an undirected graph $G=(V,E)$. It is helpful to regard each edge in $E$ as a pair of ...


4

I had an answer here involving apex graphs but it fails the definition of not having an explicit obstruction set given in this question: there is a published algorithm for finding the obstruction set, even though is too slow to run so we don't actually know what the obstruction set is. So here's another parameterizable family of answers without that flaw (...


4

The 2004 Gödel Prize was shared between the papers: The Topological Structure of Asynchronous Computation. By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923 Wait-Free k-Set Agreement Is Impossible: The Topology of Public Knowledge. By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483. Quotes ...


4

Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been characterized using topology. Defining Liveness Alpern and Schneider Safety and Liveness in Branching time Manolios et. al.


3

(All of the below is assuming your graphs are connected.) Every isotopy class of graphs with $e$ edges embedded in the sphere (which is almost the plane) corresponds to a pair of permutations $\sigma,\tau$ on $2e$ letters which satisfy $(\sigma\tau)^2 = 1$, and $\sigma,\tau$ are determined up to simultaneous conjugacy (the dual graph corresponds to the pair ...


3

The additional constraint amounts to saying that the input DAG has width $\leq k$, i.e., there is no antichain of size $k+1$. In this case, if $k$ is a constant, the decision version of the constrained topological sorting problem is in NL by Prop C.2 of https://arxiv.org/abs/1707.04310, which amounts to a PTIME dynamic programming algorithm. Reconstructing a ...


2

Regarding (3), yes, if a graph $M$ has two vertex disjoint non-planar induced subgraphs $G$ and $H$, then $G\cup H$ (and hence $M$) is not toroidal. I don't know a reference but here's a proof sketch. Thinking of the torus as $T=S^1\times S^1$, if a non-planar $G$ is embedded without crossing on $T$ then its edges must meet every $S^1\times\{a\}$ and $\{a\...


1

Iterate DAG-Shortest-Paths (in Cormen, Lesierson, Rivest, and Stein's text "Introduction to Algorithms").


1

[Reposting comment as an answer, based on the OP's response to the comment.] For a combinatorial definition, it seems like what you're looking for is a circular ordering around the vertices together with a map $f$ from the set of components to the set of faces such that $f(C_i)$ is the face of the graph that contains the component $C_i$. If you prefer a ...


1

Archdeacon's survey Topological Graph Theory was almost mentioned already: http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf


Only top voted, non community-wiki answers of a minimum length are eligible