Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021
Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
Vol. 27, no. 2, pp. 71-94, 2023. Regular paper.
Abstract 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.

 This work is licensed under the terms of the CC-BY license.
Submitted: November 2021.
Reviewed: March 2022.
Revised: April 2022.
Accepted: October 2022.
Final: October 2022.
Published: February 2023.
Communicated by Ignaz Rutter and Helene Purchase
article (PDF)