4
$\begingroup$

I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below.

  1. Since toroidal graphs can be recognized in $P$ , what are some different known characterizations of toroidal graphs ?

  2. There are more than thousand forbidden minors for toroidal graph class, and only four of them does not contain $K_{3,3}$ as a subdivision (This paper). Where can i find a bigger list of forbidden structures of toroidal graphs ?

  3. Two disjoint copies of $K_5$'s are not toroidal. Is it true that if a graph $G$ have two vertex disjoint non-planar induced subgraphs, then $G$ is not a toridal ? If not, then what is special about disjoint copies of $K_5$'s ?

$\endgroup$
2
$\begingroup$

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\}\times S^1$, or else we cut such a circle out and realize $G$ as planar. By tracing where they so meet we obtain a subgraph of $G$ realized as homotopic to some $$\left(\{a\}\times S^1\right)\cup \left(S^1\times\{b\}\right)$$ (so two circles meet in $(a,b)$). Similarly for the second graph $H$ and say $$\left(\{c\}\times S^1\right)\cup \left(S^1\times\{d\}\right).$$ But then $G$ and $H$ are not disjoint (they share a vertex or have crossing edges) as the embedded graphs meet in $(a,d)$ and $(c,b)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.