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.
WOS:000307088100026
2011
978-3-642-25869-5
Berlin
12
Lecture Notes in Computer Science; 6986
283
294
REVIEWED
Event name | Event place | Event date |
Tepla Monastery, CZECH REPUBLIC | JUN 21-24, 2011 | |