An effective crossing minimisation heuristic based on star insertion

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
21 Downloads (Pure)

Abstract

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
Volume23
Issue number2
DOIs
Publication statusPublished - Feb 2019

Bibliographical note

© retained by the authors

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

Cite this