Tangling and Untangling Trees on Point-sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908503687299072 |
|---|---|
| author | Di Battista, Giuseppe Liotta, Giuseppe Patrignani, Maurizio Symvonis, Antonios Tollis, Ioannis G. |
| author_facet | Di Battista, Giuseppe Liotta, Giuseppe Patrignani, Maurizio Symvonis, Antonios Tollis, Ioannis G. |
| contents | We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set $S$ of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let $T$ be a tree, $\vartheta(T)$ be its thrackle number, and $χ$ be any integer in the interval $[0,\vartheta(T)]$. In the tangling phase we compute a topological linear embedding of $T$ with $\vartheta(T)$ edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach $χ$ crossings. The computed linear embedding is used to construct a drawing of $T$ on $S$ with $χ$ crossings and constant curve complexity. Our approach gives rise to an $O(n^2)$-time algorithm for general trees and an $O(n \log n)$-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are $\fracπ{2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18535 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tangling and Untangling Trees on Point-sets Di Battista, Giuseppe Liotta, Giuseppe Patrignani, Maurizio Symvonis, Antonios Tollis, Ioannis G. Computational Geometry We study a question that lies at the intersection of classical research subjects in Topological Graph Theory and Graph Drawing: Computing a drawing of a graph with a prescribed number of crossings on a given set $S$ of points, while ensuring that its curve complexity (i.e., maximum number of bends per edge) is bounded by a constant. We focus on trees: Let $T$ be a tree, $\vartheta(T)$ be its thrackle number, and $χ$ be any integer in the interval $[0,\vartheta(T)]$. In the tangling phase we compute a topological linear embedding of $T$ with $\vartheta(T)$ edge crossings and a constant number of spine traversals. In the untangling phase we remove edge crossings without increasing the spine traversals until we reach $χ$ crossings. The computed linear embedding is used to construct a drawing of $T$ on $S$ with $χ$ crossings and constant curve complexity. Our approach gives rise to an $O(n^2)$-time algorithm for general trees and an $O(n \log n)$-time algorithm for paths. We also adapt the approach to compute RAC drawings, i.e. drawings where the angles formed at edge crossings are $\fracπ{2}$. |
| title | Tangling and Untangling Trees on Point-sets |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2508.18535 |