Michael J. Pelsmajer ; Marcus Schaefer ; Daniel Štefankovič - Removing Even Crossings

dmtcs:3430 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3430
Removing Even CrossingsArticle

Authors: Michael J. Pelsmajer 1; Marcus Schaefer 2; Daniel Štefankovič 3

  • 1 Department of Applied Mathematics
  • 2 Department of Computer Science [Chicago]
  • 3 Department of Computer Science [Rochester]

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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Hanani's theorem,Tutte's theorem,even crossings,crossing number,odd crossing number,independent odd crossing number,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

7 Documents citing this article

Consultation statistics

This page has been seen 236 times.
This article's PDF has been downloaded 414 times.