An effective crossing minimisation heuristic based on star insertion
Vol. 23, no. 2, pp. 135-166, 2019. Regular paper.
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.
Submitted: May 2018.
Reviewed: November 2018.
Revised: January 2019.
Accepted: February 2019.
Final: February 2019.
Published: February 2019.
Communicated by Giuseppe Liotta
article (PDF)