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.

$\endgroup$
  • $\begingroup$ This may be useful: arxiv.org/abs/math/0411488 $\endgroup$ – Jeffε Mar 23 '12 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$ – John Moeller Mar 23 '12 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 '12 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 '13 at 16:21
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.

$\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.