Removing Even Crossings

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.
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.105-110, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184387
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:39:02
Dernière modification le : jeudi 11 mai 2017 - 01:02:52
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:05:37

Fichier

dmAE0121.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184387, version 1

Collections

Citation

Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing Even Crossings. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.105-110, 2005, DMTCS Proceedings. 〈hal-01184387〉

Partager

Métriques

Consultations de la notice

34

Téléchargements de fichiers

65