Geodesic
Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021 , Tome 27 (2023) no. 2, pp. 71-94.

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

We present a thorough experimental evaluation of several crossing minimization heuristics that are based on the construction and iterative improvement of a planarization, i.e., a planar representation of a graph with crossings replaced by dummy vertices. The evaluated heuristics include variations and combinations of the well-known planarization method, the recently implemented star reinsertion method, and a new approach proposed herein: the mixed insertion method. Our experiments reveal the importance of several implementation details such as the detection of non-simple crossings (i.e., crossings between adjacent edges, multiple crossings between the same two edges, or crossings of an edge with itself). The most notable finding, however, is that the insertion of stars in a fixed embedding setting is not only significantly faster than the insertion of edges in a variable embedding setting, but also leads to solutions of higher quality.
DOI : 10.7155/jgaa.00615
Keywords: Crossing number, Experimental evaluation, Algorithm engineering 
@article{JGAA_2023_27_2_a3,
     author = {Markus Chimani and Max Ilsen and Tilo Wiedera},
     title = {Star-Struck by {Fixed} {Embeddings:} {Modern} {Crossing} {Number} {Heuristics}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {71--94},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2023},
     doi = {10.7155/jgaa.00615},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00615/}
}
TY  - JOUR
AU  - Markus Chimani
AU  - Max Ilsen
AU  - Tilo Wiedera
TI  - Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 71
EP  - 94
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00615/
DO  - 10.7155/jgaa.00615
LA  - en
ID  - JGAA_2023_27_2_a3
ER  - 
%0 Journal Article
%A Markus Chimani
%A Max Ilsen
%A Tilo Wiedera
%T Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
%J Journal of Graph Algorithms and Applications
%D 2023
%P 71-94
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00615/
%R 10.7155/jgaa.00615
%G en
%F JGAA_2023_27_2_a3
Markus Chimani; Max Ilsen; Tilo Wiedera. Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021
					, Tome 27 (2023) no. 2, pp. 71-94. doi : 10.7155/jgaa.00615. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00615/

Cité par Sources :