# Decomposing graphs of genus one

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.

• This may be useful: arxiv.org/abs/math/0411488 Mar 23 '12 at 11:00
• 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. Mar 23 '12 at 19:27
• 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.) Mar 23 '12 at 19:30
• 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. Sep 29 '13 at 16:21