2026-07-19T23:43:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24994 2025-11-26T06:44:53Z ddc:004 open_access

Tangling and Untangling Trees on Point-Sets Di Battista, Giuseppe Liotta, Giuseppe Patrignani, Maurizio Symvonis, Antonios Tollis, Ioannis G. Tree drawings Prescribed edge crossings Thrackle Curve complexity Point-set embeddings RAC drawings Topological linear embeddings 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, ϑ(T) be its thrackle number, and χ be any integer in the interval [0,ϑ(T)]. In the tangling phase we compute a topological linear embedding of T with ϑ(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²)-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 π/2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giuseppe Di Battista and Giuseppe Liotta and Maurizio Patrignani and Antonios Symvonis and Ioannis G. Tollis 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.8 urn:nbn:de:0030-drops-249947 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode