Removing even crossings

• Autores: Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
• Localización: Journal of combinatorial theory. Series B, ISSN 0095-8956, Vol. 97, Nº. 4, 2007, págs. 489-500
• Idioma: inglés
• DOI: 10.1016/j.jctb.2006.08.001
• Texto completo no disponible (Saber más ...)
• Resumen

  • An edge in a drawing of a graph is called 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 so that its even edges are not involved in any intersections. We give a new and significantly simpler proof of the stronger statement that the redrawing can be done in such a way that no new odd intersections are introduced. We include two applications of this strengthened result: an easy proof of a theorem of Hanani and Tutte (the only proof we know of not to use Kuratowski's theorem), and the new result that the odd crossing number of a graph equals the crossing number of the graph for values of at most 3. The paper begins with a disarmingly simple proof of a weak (but standard) version of the theorem by Hanani and Tutte.