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
NULL##NULL##NULL
Michael J. Pelsmajer;Marcus Schaefer;Daniel Štefankovič
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.
Michael J. Pelsmajer;Marcus Schaefer;Daniel Štefankovič, Springer eBooks, Crossing Number of Graphs with Rotation Systems, pp. 3-12, 2008, 10.1007/978-3-540-77537-9_3.
Michael J. Pelsmajer;Marcus Schaefer;Daniel Štefankovič, Springer eBooks, Crossing Numbers and Parameterized Complexity, pp. 31-36, 2008, 10.1007/978-3-540-77537-9_6.
Michael J. Pelsmajer;Marcus Schaefer;Daniel Štefankovič, Lecture notes in computer science, Odd Crossing Number Is Not Crossing Number, pp. 386-396, 2006, 10.1007/11618058_35, https://doi.org/10.1007/11618058_35.