Hanani-Tutte and Monotone Drawings

A drawing of a graph is x-monotone if every edge intersects every vertical line at most once and every vertical line contains at most one vertex. Pach and Toth showed that if a graph has an x-monotone drawing in which every pair of edges crosses an even number of times, then the graph has an x-monotone embedding in which the x-coordinates of all vertices are unchanged. We give a new proof of this result and strengthen it by showing that the conclusion remains true even if adjacent edges are allowed to cross oddly. This answers a question posed by Pach and Toth. Moreover, we show that an extension of this result for graphs with non-adjacent pairs of edges crossing oddly fails even if there exists only one such pair in a graph.


Editor(s):
Kolman, P
Kratochvil, J
Published in:
Graph-Theoretic Concepts In Computer Science, 6986, 283-294
Presented at:
37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), Tepla Monastery, CZECH REPUBLIC, JUN 21-24, 2011
Year:
2011
Publisher:
Berlin, Springer-Verlag Berlin
ISSN:
0302-9743
ISBN:
978-3-642-25869-5
Laboratories:




 Record created 2013-02-28, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)