Removing Even Crossings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

Removing Even Crossings

Résumé

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.
Fichier principal
Vignette du fichier
dmAE0121.pdf (140.99 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184387 , version 1 (14-08-2015)

Identifiants

Citer

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, ⟨10.46298/dmtcs.3430⟩. ⟨hal-01184387⟩

Collections

TDS-MACS
31 Consultations
557 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More