15
$\begingroup$

Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components.

Is there such a "nice" decomposition of graphs of genus one ?

In their seminal work on graph minors, Roberston and Seymour showed that every minor-free graph can be decomposed into a "clique-sum" of "almost planar" graphs. This, of course, applies to bounded-genus graphs also. I am looking for decompositions specific to graphs of genus one, to better understand their structural properties.

Improve this question
$\endgroup$
4
  • $\begingroup$ This may be useful: arxiv.org/abs/math/0411488 $\endgroup$
    – Jeffε
    Mar 23, 2012 at 11:00
  • $\begingroup$ Ah, thanks Jeff. Tangentially related to the question, I'd been puzzling about how to embed $K_7$ on the torus and I hadn't been able to figure it out. $\endgroup$
    – Josephine Moeller
    Mar 23, 2012 at 19:27
  • $\begingroup$ There is a stronger decomposability result for graph families which exclude a single-crossing graph as a minor (i.e. a graph which can be drawn in the plane with a single point where edges cross). Such graphs can be decomposed into cliquesums of planar graphs and constant-treewidth graphs (see e.g. "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors"). If there's a single-crossing graph in the obstruction set for the torus this would help you. (I'm not sure there is though - and there might be a simple reason there cannot be.) $\endgroup$
    – Bart Jansen
    Mar 23, 2012 at 19:30
  • $\begingroup$ There is a simple reason why there cannot be a one-crossing obstruction to toroidality: every one-crossing graph can be drawn on the torus, by replacing the crossing by a small handle. $\endgroup$
    – David Eppstein
    Sep 29, 2013 at 16:21

1 Answer 1

Reset to default
1
$\begingroup$

I think that Robertson and Seymour showed that every minor-free graph can be decomposed into a "clique-sum" of "almost bounded genus" graphs. The basic building blocks are not planar graphs but graphs of bounded genus (genus depending on the excluded minor). I think that toroidal graphs are not decomposable any further.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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