Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

DOI10.1007/978-3-030-92931-2_3arXiv2108.11443MaRDI QIDQ6376022FDOQ6376022

Tilo Wiedera, Markus Chimani, Max Ilsen

Publication date: 25 August 2021

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 or multiple crossings between the same two edges). 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.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6376022)