Hanani–Tutte, Monotone Drawings, and Level-Planarity

Radoslav Fulek (), Michael J. Pelsmajer (), Marcus Schaefer () and Daniel Štefankovič ()
Additional contact information
Radoslav Fulek: Ecole Polytechnique Fédérale de Lausanne
Michael J. Pelsmajer: Illinois Institute of Technology, Department of Applied Mathematics
Marcus Schaefer: DePaul University, Department of Computer Science
Daniel Štefankovič: University of Rochester, Computer Science Department

A chapter in Thirty Essays on Geometric Graph Theory, 2013, pp 263-287 from Springer

Abstract: Abstract 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 each other oddly. This answers a question posed by Pach and Tóth. We show that a further strengthening to a “removing even crossings” lemma is impossible by separating monotone versions of the crossing and the odd crossing number. Our results extend to level-planarity, which is a well-studied generalization of x-monotonicity. We obtain a new and simple algorithm to test level-planarity in quadratic time, and we show that x-monotonicity of edges in the definition of level-planarity can be relaxed.

Keywords: Planning Level; Hanani Tutte Theorem; Monotone Drawings; Level Planarity Testing; Edge Crossings (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4614-0110-0_14

Ordering information: This item can be ordered from
http://www.springer.com/9781461401100

DOI: 10.1007/978-1-4614-0110-0_14

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().