Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Hanani-Tutte and Monotone Drawings
verfasst von : Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 Tóth 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 Tóth. 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.