6
votes
Accepted
Complexity of isotopy of embedded graphs
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 ...
- 824
4
votes
Accepted
Dual of cut of embedded graph disconnects surface
I assume that you require that all faces of $G$ are topological disks. After cutting along $C^*$, each face is a topological disk bounded by either a cycle of $G$, or a cycle that consists of two arcs ...
- 617
4
votes
Accepted
Minor closed properties that are explicitly MSO expressible
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, ...
- 50.9k
3
votes
Complexity of isotopy of embedded graphs
(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,...
- 376
3
votes
Accepted
Constrained Topological Sorting with bounded number of chains
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 ...
- 8,896
2
votes
Properties of toroidal graph
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 ...
- 4,475
1
vote
Is there any good and free Introduction to topological graph theory
Archdeacon's survey Topological Graph Theory was almost mentioned already:
http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf
- 4,475
Only top scored, non community-wiki answers of a minimum length are eligible