Geodesic
Removing Even Crossings
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a39,
     author = {Pelsmajer, Michael J. and Schaefer, Marcus and \v{S}tefankovi\v{c}, Daniel},
     title = {Removing {Even} {Crossings}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3430},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3430/}
}
TY  - JOUR
AU  - Pelsmajer, Michael J.
AU  - Schaefer, Marcus
AU  - Štefankovič, Daniel
TI  - Removing Even Crossings
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3430/
DO  - 10.46298/dmtcs.3430
LA  - en
ID  - DMTCS_2005_special_250_a39
ER  - 
%0 Journal Article
%A Pelsmajer, Michael J.
%A Schaefer, Marcus
%A Štefankovič, Daniel
%T Removing Even Crossings
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3430/
%R 10.46298/dmtcs.3430
%G en
%F DMTCS_2005_special_250_a39
Pelsmajer, Michael J.; Schaefer, Marcus; Štefankovič, Daniel. Removing Even Crossings. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3430. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3430/

Cité par Sources :