Geodesic
Advances in the Planarization Method: Effective Multiple Edge Insertions
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011 , Tome 16 (2012) no. 3, pp. 729-757.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The planarization method is the strongest known method to heuristically find good solutions to the general crossing number problem in graphs: Starting from a planar subgraph, one iteratively inserts edges, representing crossings via dummy vertices. In the recent years, several improvements both from the practical and the theoretical point of view have been made. We review these advances and conduct an extensive study of the algorithms' practical implications. Thereby, we also present the first implementation of an approximation algorithm for the crossing number problem of general graphs. We compare the obtained results with known exact crossing number solutions and show that modern techniques allow surprisingly tight results in practice. 
@article{JGAA_2012_16_3_a5,
     author = {Markus Chimani and Carsten Gutwenger},
     title = {Advances in the {Planarization} {Method:} {Effective} {Multiple} {Edge} {Insertions}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {729--757},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2012},
     doi = {10.7155/jgaa.00264},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00264/}
}
TY  - JOUR
AU  - Markus Chimani
AU  - Carsten Gutwenger
TI  - Advances in the Planarization Method: Effective Multiple Edge Insertions
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 729
EP  - 757
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00264/
DO  - 10.7155/jgaa.00264
LA  - en
ID  - JGAA_2012_16_3_a5
ER  - 
%0 Journal Article
%A Markus Chimani
%A Carsten Gutwenger
%T Advances in the Planarization Method: Effective Multiple Edge Insertions
%J Journal of Graph Algorithms and Applications
%D 2012
%P 729-757
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00264/
%R 10.7155/jgaa.00264
%G en
%F JGAA_2012_16_3_a5
Markus Chimani; Carsten Gutwenger. Advances in the Planarization Method: Effective Multiple Edge Insertions. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Nineteenth International Symposium on Graph Drawing, GD 2011
					, Tome 16 (2012) no. 3, pp. 729-757. doi : 10.7155/jgaa.00264. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00264/

Cité par Sources :