Discrete Mathematics & Theoretical Computer Science (Jan 2005)

Removing Even Crossings

  • Michael J. Pelsmajer,
  • Marcus Schaefer,
  • Daniel Štefankovič

DOI
https://doi.org/10.46298/dmtcs.3430
Journal volume & issue
Vol. DMTCS Proceedings vol. AE,..., no. Proceedings

Abstract

Read online

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.

Keywords