Home | Issues | About JGAA | Instructions for Authors |
Special issue on Selected papers from the Twenty-nineth International Symposium on Graph Drawing and Network Visualization, GD 2021
DOI: 10.7155/jgaa.00615
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.
|
Journal Supporters
|