Unbent Collections of Orthogonal Drawings

Todor Antić, Giuseppe Liotta, Tomáš Masařík, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink · 2025

Read Unbent Collections of Orthogonal Drawings by Todor Antić, Giuseppe Liotta, Tomáš Masařík, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink (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-2502-18390.txt.

Introduction

Todor Antić and co-authors wrote a 2025 paper on drawing graphs with right-angle edges. A recent trend shows one graph through several drawings instead of a single crowded picture. The authors ask whether every flat graph with at most four links per point can be drawn so that each edge is straight, with no bends, in at least one drawing.

They prove that three drawings always suffice, and that no smaller number works in general. They also give exact rules for when two drawings are enough. A second goal was cutting the total bends across all drawings. They show that task is NP-hard, yet they offer a method that stays within three times the best count. Special cases get exact answers too.

Catalog record

CREATORTodor Antić, Giuseppe Liotta, Tomáš Masařík, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE122 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-18390

Browse the full library · About the Tower of Babel

Full text

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

Unbent Collections of Orthogonal Drawings Todor Antić, Giuseppe Liotta, Tomáš Masařík, Giacomo Ortali, Matthias Pfretzschner, Peter Stumpf, Alexander Wolff, Johannes Zink Abstract Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we apply this idea to orthogonal graph drawing. Due to the orthogonal drawing style, we focus on 4-graphs, that is, graphs of maximum degree 4. We restrict ourselves to plane graphs, that is, planar graphs whose embedding is fixed. Our goal is to represent any plane 4-graph G G by an unbent collection , that is, a collection of orthogonal drawings of G G that adhere to the embedding of G G and ensure that each edge of G G is drawn without bends in at least one of the drawings. We investigate two objectives. First, we consider minimizing the number of drawings in an unbent collection. We prove that every plane 4-graph can be represented by a collection with at most three drawings, which is tight. We also give necessary and sufficient conditions for a graph to admit an unbent collection of size 2 2 . Second, we consider minimizing the total number of bends over all drawings in an unbent collection. We show that this problem is NP-hard and give a 3-approximation algorithm. For the special case of plane triconnected cubic graphs, we show how to compute minimum-bend collections in linear time. Charles University, Prague, Czech [email protected]://orcid.org/0009-0008-6521-7987Supported by Czech Science Foundation grant no. 23-04949X and grant no. SVV–2023–260699. Università degli Studi di Perugia, Perugia, [email protected]://orcid.org/0000-0002-2886-9694Research supported in part by MUR of Italy, PRIN Project no. 2022TS4Y3N – EXPAND and PON Project ARS01_00540. University of Warsaw, Warsaw, [email protected]://orcid.org/0000-0001-8524-4036Supported by the Polish National Science Centre SONATA-17 grant number 2021/43/D/ST6/03312. Università degli Studi di Perugia, Perugia, [email protected] Universität Passau, Passau, [email protected]://orcid.org/0000-0002-5378-1694Funded by the Deutsche Forschungsgemeinschaft (DFG) – grant 541433306. Charles University, Prague, Czech Republic Czech Technical University in Prague, Czech [email protected]://orcid.org/0000-0003-0531-9769Supported by Czech Science Foundation grant no. 23-04949X Universität Würzburg, Würzburg, Germanyhttps://orcid.org/0000-0001-5872-718X Technische Universität München, Heilbronn, [email protected]://orcid.org/0000-0002-7398-718X We thank the organizers of the Homonolo Workshop 2023, where this work started. keywords Orthogonal drawings, Bend minimization, Unbent collection ccs Theory of computation Design and analysis of algorithms ccs Theory of computation Approximation algorithms analysis ccs Human-centered computing Graph drawings ccs Mathematics of computing \rightarrow Graph theory † † runningauthor: Antić, Liotta, Masařík, Ortali, Pfretzschner, Stumpf, Wolff, and Zink 1 Introduction A way to determine the quality of a drawing of a graph is its readability , which, informally speaking, is the extent to which a drawing conveys the structure of the graph it represents. More formally, readability translates into a set of goals that a graph drawing algorithm must optimize. For example, in the context of orthogonal graph drawing, the typical objectives are crossing minimization and bend minimization. These objectives typically oppose each other: reducing the number of crossings may lead to adding bends along the edges, and vice versa. Related work. A recent research direction is to represent a graph by a collection or sequence of different drawings, each of which optimizes the readability of a particular subgraph, possibly at the expense of the rest. One contribution in this direction is the so-called storyplan approach, where a graph is represented by a sequence of drawings, called frames , each of which only shows a restricted (e.g., planar) subgraph. To see the whole (complicated) graph means to watch all (relatively simple) frames [ 4 , 7 ] . Another contribution are graph stories , where each frame contains the same number of vertices, vertices are shown in an interval of consecutive frames, and, for each vertex, the index of the first frame when it appears is given as input. As in a storyplan, it is required that the drawing of an edge and the position of a vertex is the same in every frame where the edge or the vertex appears. The task is to compute graph stories with specific properties (e.g., crossing-free frames [ 3 ] ). Another approach is to visualize the graph by means of a collection of drawings, each of which includes all vertices and edges, but to optimize the drawings only with respect to specific subgraphs. Hliněný and Masařík [ 9 ] adopted this idea and introduced the problem of representing a non-planar graph G via multiple drawings such that G is fully represented in each drawing and each edge of G is not crossed in at least one of the drawings. They called such a collection an uncrossed collection . The size of a collection is the number of drawings it contains. Hliněný and Masařík studied two optimization problems. For a given graph G , the first problem called the uncrossed number is to find a minimum-size uncrossed collection of G . The second problem is to find an uncrossed collection that minimizes the total number of crossings over all drawings, for which they showed an NP-hardness and an FPT algorithm parameterized by the solution size. Recently, the authors of [ 2 ] determined the uncrossed number of complete and complete bipartite graphs exactly. They also gave a lower bound for the uncrossed number of general graphs in terms of vertex and edge numbers. Our contribution. We revisit the classical problem of computing a planar orthogonal layout with the minimum number of bends from the “collection perspective” of Hliněný and Masařík. Namely, we study the following problem: Given a plane 4-graph G (i.e., a planar graph with vertex degree at most 4 and with a fixed planar embedding), compute a set of planar orthogonal drawings of G such that every edge of G is straight (i.e., has no bend) in at least one drawing of the collection. Analogously to the terminology of Hliněný and Masařík, we call such a collection an unbent collection . We study two problems. For a given graph G , we want to find an unbent collection of minimum size, \operatorname{un}(G) , and an unbent collection that minimizes the total number of bends, \operatorname{tbn}(G) . Refer to Figure 1 . {subfigure} 0.28 \subcaption {subfigure} .68 \subcaption Figure 1: (a) A minimum-bend orthogonal drawing of K_{4} . (b) An unbent collection for K_{4} with two drawings showing that \operatorname{un}(K_{4})=2 and \operatorname{tbn}(K_{4})\leq 12 (in fact, \operatorname{tbn}(K_{4})=12 ); see Definition 1 . Red edges are straight, whereas blue edges are bent. Specifically, we show the following. For every plane 4-graph, an unbent collection of size 3 always exists (this is tight) and can be found in almost-linear time; see Theorem 3 . We also give a necessary and sufficient condition for graphs to have an unbent collection of size 2. The condition is based on a new concept of balanced 2-edge-coloring that we introduce in Section 2 . Then, we show that it is NP-hard to decide, given a plane 4-graph G and a positive integer k , whether G admits an unbent collection with at most k bends; see Section 3 . Note that if the embedding of G is not fixed, it is even NP-hard to decide whether G admits a (single) drawing without bends [ 8 ] . Next, we give a 3-approximation algorithm for minimizing

Read the complete text