<p>I think that Robertson and Seymour showed that every minor-free graph can be decomposed into a "clique-sum" of "<strong>almost bounded genus</strong>" 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.</p>

CC BY-SA 3.0
2012-04-25T05:39:54.330Z
2012-04-25T05:39:54.330Z
Marcin Kamiński
<p>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.</p>

<blockquote>
  <p>Is there such a "nice" decomposition of graphs of genus one ?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2012-03-23T11:00:28.493Z
This may be useful: http://arxiv.org/abs/math/0411488
Jeffε
CC BY-SA 3.0
2012-03-23T19:27:05.840Z
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.
Josephine Moeller
CC BY-SA 3.0
2012-03-23T19:30:33.087Z
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.)
Bart Jansen
CC BY-SA 3.0
2013-09-29T16:21:30.387Z
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.
David Eppstein
<graph-theory><co.combinatorics><planar-graphs><graph-minor>
Decomposing graphs of genus one
Shiva Kintali
# Decomposing graphs of genus one

(Asked by: username_0 on 2012-03-22)

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.

**Tags:** graph-theory, co.combinatorics, planar-graphs, graph-minor
> **Comments:**
> **username_1**: This may be useful: http://arxiv.org/abs/math/0411488  
> **username_2**: 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.  
> **username_3**: 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.)  
> **username_4**: 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.  

---

## 1 answers

### Answer by username_5 on 2012-04-25. Score: 1

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.


---

