| Title: |
Drawing Reeb Graphs |
| Authors: |
Chambers, Erin; Fasy, Brittany Terese; Hosseini Sereshgi, Erfan; Löffler, Maarten; Sub Geometric Computing; Fernau, Henning; Zhu, Binhai |
| Publication Year: |
2025 |
| Subject Terms: |
Graph Drawing; Minimum Crossing; Reeb Graphs; Taverne; Theoretical Computer Science; General Computer Science |
| Description: |
Reeb graphs are simple topological descriptors with applications in topological data analysis and computational geometry. Despite their prevalence, visualization of Reeb graphs has received less attention. In this paper, we bridge an essential gap in the literature by exploring the complexity of drawing Reeb graphs. Specifically, we demonstrate that Reeb graph crossing number minimization is NP-hard, both for straight-lined and curved edges. On the other hand, we identify specific classes of Reeb graphs, namely paths and caterpillars, for which crossing-free drawings exist. We also give an optimal algorithm for drawing cycle-shaped Reeb graphs with the least number of crossings and provide initial observations on the complexities of drawing multi-cycle Reeb graphs. We hope that this work establishes the foundation for an understanding of the graph drawing challenges inherent in Reeb graph visualization and paves the way for future work in this area. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
0302-9743 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/483023 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/483023 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.B0B3BB75 |
| Database: |
BASE |