An effective crossing minimisation heuristic based on star insertion

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
38 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)135-166
Number of pages32
JournalJournal of Graph Algorithms and Applications
Issue number2
Publication statusPublished - Feb 2019

Bibliographical note

© retained by the authors


Dive into the research topics of 'An effective crossing minimisation heuristic based on star insertion'. Together they form a unique fingerprint.

Cite this