Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911379687997440 |
|---|---|
| author | Chimani, Markus Ilsen, Max Wiedera, Tilo |
| author_facet | Chimani, Markus Ilsen, Max Wiedera, Tilo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_11443 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics Chimani, Markus Ilsen, Max Wiedera, Tilo Discrete Mathematics Data Structures and Algorithms Combinatorics 68R10 (Primary) 05C10, 90C27 (Secondary) G.2.1; G.2.2; F.2.2 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. |
| title | Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics 68R10 (Primary) 05C10, 90C27 (Secondary) G.2.1; G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2108.11443 |