Geodesic
An effective crossing minimisation heuristic based on star insertion
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 135-166.

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

We present a new heuristic method for minimising crossings in a graph. The method is based upon repeatedly solving the so-called star insertion problem in the setting where the combinatorial embedding is fixed, and has several desirable characteristics for practical use. We introduce the method, discuss some aspects of algorithm design for our implementation, and provide some experimental results. The results indicate that our method compares well to existing methods, and also that it is suitable for dense instances.
DOI : 10.7155/jgaa.00487
Keywords: Crossing number, Heuristic, Graph drawing, Star insertion 
@article{JGAA_2019_23_2_a1,
     author = {Kieran Clancy and Michael Haythorpe and Alex Newcombe},
     title = {An effective crossing minimisation heuristic based on star insertion},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {135--166},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2019},
     doi = {10.7155/jgaa.00487},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00487/}
}
TY  - JOUR
AU  - Kieran Clancy
AU  - Michael Haythorpe
AU  - Alex Newcombe
TI  - An effective crossing minimisation heuristic based on star insertion
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 135
EP  - 166
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00487/
DO  - 10.7155/jgaa.00487
LA  - en
ID  - JGAA_2019_23_2_a1
ER  - 
%0 Journal Article
%A Kieran Clancy
%A Michael Haythorpe
%A Alex Newcombe
%T An effective crossing minimisation heuristic based on star insertion
%J Journal of Graph Algorithms and Applications
%D 2019
%P 135-166
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00487/
%R 10.7155/jgaa.00487
%G en
%F JGAA_2019_23_2_a1
Kieran Clancy; Michael Haythorpe; Alex Newcombe. An effective crossing minimisation heuristic based on star insertion. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 135-166. doi : 10.7155/jgaa.00487. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00487/

Cité par Sources :