Skip to Main content Skip to Navigation
Conference papers

Removing Even Crossings

Abstract : An edge in a drawing of a graph is called $\textit{even}$ if it intersects every other edge of the graph an even number of times. Pach and Tóth proved that a graph can always be redrawn such that its even edges are not involved in any intersections. We give a new, and significantly simpler, proof of a slightly stronger statement. We show two applications of this strengthened result: an easy proof of a theorem of Hanani and Tutte (not using Kuratowski's theorem), and the result that the odd crossing number of a graph equals the crossing number of the graph for values of at most $3$. We begin with a disarmingly simple proof of a weak (but standard) version of the theorem by Hanani and Tutte.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184387
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:39:02 AM
Last modification on : Thursday, July 4, 2019 - 2:10:02 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:05:37 AM

File

dmAE0121.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing Even Crossings. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.105-110, ⟨10.46298/dmtcs.3430⟩. ⟨hal-01184387⟩

Share

Metrics

Record views

29

Files downloads

414