Tangling and Untangling Trees on Point-sets

Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis · 2025

Read Tangling and Untangling Trees on Point-sets by Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18535.txt.

Introduction

Giuseppe Di Battista and co-authors study how to draw trees on fixed point sets in a 2025 paper. A drawing can aim for a set number of edge crossings while keeping each edge's bends few. The work sits where graph theory meets graph drawing.

First, in a tangling phase, the team lay a tree out with its top crossing count and few spine passes. Next, in an untangling phase, they strip crossings down to any target count without adding passes. The layout then turns into a point-set drawing with the same counts. Run times are given for plain trees and for paths. A right-angle variant is also covered.

Catalog record

CREATORGiuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18535

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tangling and Untangling Trees on Point-sets Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis Abstract 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 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 T be a tree, ϑ ⁡ ( T ) \vartheta(T) be its thrackle number, and χ \chi be any integer in the interval [ 0 , ϑ ⁡ ( T ) ] [0,\vartheta(T)] . In the tangling phase we compute a topological linear embedding of T T with ϑ ⁡ ( T ) \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 χ \chi crossings. The computed linear embedding is used to construct a drawing of T T on S S with χ \chi crossings and constant curve complexity. Our approach gives rise to an O ⁡ ( n 2 ) O(n^{2}) -time algorithm for general trees and an O ⁡ ( n ​ log ⁡ n ) 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 \frac{\pi}{2} . \captionsetup [subfigure]justification=centering Roma Tre University, Rome, [email protected]://orcid.org/0000-0003-4224-1550 University of Perugia, Perugia, [email protected]://orcid.org/0000-0002-2886-9694 Roma Tre University, Rome, [email protected]://orcid.org/0000-0001-9806-7411 School of Applied Mathematical & Physical Sciences, NTUA, [email protected]://orcid.org/0000-0002-0280-741X Department of Computer Science, University of Crete, Heraklion, [email protected]://orcid.org/0000-0002-5507-7692 keywords Tree drawings, Prescribed edge crossings, Curve complexity, Point-set embeddings, RAC drawings, Topological linear embeddings ccs Mathematics of computing Graph algorithms ccs Mathematics of computing Graph theory † † runningtitle: Tangling and Untangling Trees on Point-sets † † runningauthor: Di Battista, Liotta, Patrignani, Symvonis, Tollis † † copyright: Giuseppe Di Battista, Giuseppe Liotta, Maurizio Patrignani, Antonios Symvonis, Ioannis G. Tollis 1 Introduction In this paper we study the following problem: Given an n -vertex tree T , a set S of n distinct points in the plane, and a non-negative integer \chi , find a simple drawing \Gamma of T with the following properties: (a) \Gamma is a point-set embedding of T on S , i.e. its vertices are the points of S , (b) the edges of T are represented by polylines with constant curve complexity , measured as the maximum number of bends per edge, and (c) the edges cross exactly \chi times in \Gamma . In the following we refer to them as Property a , Property b , and Property c . The problem locates itself at the intersection of three well studied research subjects in Graph Drawing and Graph Theory, namely the study of point-set embeddings, the study of drawings with limited curve complexity, and the study of drawings with prescribed numbers of edge crossings. Before describing our contribution, we briefly recall each such topic. Property a – For a graph G with n vertices and a set S of n distinct points in the plane, a point-set embedding of G on S is a drawing of G where each vertex is mapped to a distinct point of S . Most of the literature on this topic is about planar ( \chi=0 ) point-set embeddings of graphs (see, e.g., [ 2 , 3 , 5 , 7 , 19 , 27 ] ). Specifically, it is NP-complete to test if a planar graph G has a straight-line planar point-set embedding on a given point-set [ 7 ] . If G is an outerplanar graph and the points are in general position such a drawing can constructed in polynomial time (see, e.g., [ 4 , 5 ] ). Property b – Together with the edge crossing minimization, the minimization of the edge bends and/or of the bends per edge are among the oldest optimization questions in graph drawing (see, e.g., [ 9 , 22 , 32 ] ). In particular, the relationship between point-set embeddings and curve complexity has been studied when the mapping between the vertices of the graph and the points is specified as part of the input as well as when it is partially specified or not specified (see, e.g., [ 1 , 16 , 17 , 18 , 23 , 28 ] ). Notably, Kaufmann and Wiese proved that when the mapping is not specified a planar graph admits a crossing-free point-set embedding with constant curve complexity, namely at most two bends per edge [ 23 ] . Property c – The thrackle bound \vartheta(G) of a graph G=(V,E) with m=|E| edges is the number of crossings that a drawing of G would have if every edge crosses every other non-adjacent edge exactly once. It is well known that \vartheta(G)=(m(m+1)-\sum_{v\in V}\deg^{2}(v))/2 ; see, e.g., [ 30 , 31 ] . As an example, for a cycle C_{n} with n vertices the above formula gives \vartheta(C_{n})=n(n-3)/2 . For a path P_{n} with n vertices, where all but two vertices have degree two, the formula gives \vartheta(P_{n})=(n-2)(n-3)/2 . A thrackle is a drawing of a graph G with exactly \vartheta(G) crossings. Not all graphs admit thrackles. For example, a cycle C_{4} with 4 vertices does not admit a drawing with \vartheta(C_{4})=2 crossings. As reported in [ 33 ] , Conway conjectured in 1969 that each thrackleable graph contains at most as many edges as vertices. His conjecture, known as Conway’s thrackle conjecture, still remains open. Woodall [ 33 ] was the first to work on the thrackle conjecture and, assuming the conjecture was true, showed that a finite graph admits a thrackle if and only if it contains at most one odd cycle, no 4-cycle, and each of its connected components is either a tree or it contains exactly one cycle. Refer to [ 14 , 25 , 34 ] and the references therein for progress relevant to Conway’s Thrackle conjecture. Graph classes that admit thrackles (and satisfy the thrackle conjecture) include cycles of more than 4 vertices [ 20 ] and trees [ 30 ] . Given a tree T and an integer 0\leq\chi\leq\vartheta(T) , Piazza et al. [ 30 ] presented an algorithm that constructs a drawing of T with \chi crossings and curve complexity O(n) . A similar result was presented by Harborth [ 20 ] for any cycle C_{n}~,n>4 . Hence, the algorithms in [ 30 ] and [ 20 ] compute drawings that satisfy Property c . Relationship between Properties b and c – A linear thrackle is a thrackle with curve complexity zero. Not all graphs admit linear thrackles. For example, a cycle C_{6} with 6 edges does not admit a linear thrackle with \vartheta(C_{6})=9 crossings (but it admits a thrackle [ 30 ] ). It should be noted that, as proved by Erdős [ 12 ] and Perles [ 29 ] , Conway’s conjecture holds for linear thrackles. More generally, there is a complex relationship between number of crossings and curve complexity. For example, a cycle C with an odd number of vertices admits a

Read the complete text