Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Removing Even Crossi ...
Conference paper

Removing Even Crossings

Michael J. Pelsmajer (1), Marcus Schaefer (2), Daniel Štefankovič ORCID (3)
(1) Department of Applied Mathematics
(2) Department of Computer Science [Chicago]
(3) Department of Computer Science [Rochester]
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3430
License
https://about.hal.science/hal-authorisation-v1
Indicators
601
Views
860
Downloads

Removing Even Crossings

Michael J. Pelsmajer (1), Marcus Schaefer (2), Daniel Štefankovič ORCID (3)
(1) Department of Applied Mathematics
(2) Department of Computer Science [Chicago]
(3) Department of Computer Science [Rochester]
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Hanani's theorem
  • Tutte's theorem
  • even crossings
  • crossing number
  • odd crossing number
  • independent odd crossing number
Cited by

Source: OpenCitations

  • Removing Even Crossings on Surfaces

    Electronic Notes in Discrete Mathematics

    Authors : Michael J. Pelsmajer ORCID, Marcus Schaefer ORCID, Daniel Štefankovič ORCID

    Journal reference : Volume 29, 2007, pp. 85-90

    DOI : 10.1016/j.endm.2007.07.015

  • Algebraic characterizations of outerplanar and planar graphs

    European Journal of Combinatorics

    Authors : Hein van der Holst

    Journal reference : Volume 28, 2007, pp. 2156-2166

    DOI : 10.1016/j.ejc.2007.04.005

  • Odd Crossing Number and Crossing Number Are Not the Same

    Discrete & Computational Geometry

    Authors : Michael J. Pelsmajer ORCID, Marcus Schaefer ORCID, Daniel Štefankovič ORCID

    Journal reference : Volume 39, 2008, pp. 442-454

    DOI : 10.1007/s00454-008-9058-x

  • Crossing Number of Graphs with Rotation Systems

    Lecture notes in computer science

    Authors : Michael J. Pelsmajer ORCID, Marcus Schaefer ORCID, Daniel Štefankovič ORCID

    Journal reference : Volume , 2008, pp. 3-12

    DOI : 10.1007/978-3-540-77537-9_3

  • Odd Crossing Number Is Not Crossing Number

    Lecture notes in computer science

    Authors : Michael J. Pelsmajer ORCID, Marcus Schaefer ORCID, Daniel Štefankovič ORCID

    Journal reference : Volume , 2006, pp. 386-396

    DOI : 10.1007/11618058_35

  • Note on the Pair-crossing Number and the Odd-crossing Number

    Discrete & Computational Geometry

    Authors : Géza Tóth ORCID

    Journal reference : Volume 39, 2007, pp. 791-799

    DOI : 10.1007/s00454-007-9024-z

  • Crossing Numbers and Parameterized Complexity

    Lecture notes in computer science

    Authors : Michael J. Pelsmajer ORCID, Marcus Schaefer ORCID, Daniel Štefankovič ORCID

    Journal reference : Volume , 2008, pp. 31-36

    DOI : 10.1007/978-3-540-77537-9_6
Preview
Loading PDF preview...