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 <>
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

  • HAL Id : hal-01184387, version 1

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. ⟨hal-01184387⟩

Share

Metrics

Record views

61

Files downloads

950