Skip to main content
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 ...
Arnaud's user avatar
  • 834
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 ...
Tim's user avatar
  • 627
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,...
zeb's user avatar
  • 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 ...
a3nm's user avatar
  • 9,517
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 ...
Bjørn Kjos-Hanssen's user avatar
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
Bjørn Kjos-Hanssen's user avatar

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