Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces

Patrizio Angelini, Carla Binucci, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Fabrizio Grosso, Giacomo Ortali, Ioannis G. Tollis · 2025

Read Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces by Patrizio Angelini, Carla Binucci, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Fabrizio Grosso, Giacomo Ortali, 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-2503-01526.txt.

Introduction

Patrizio Angelini and co-authors study graph drawings where every edge is a unit-length horizontal or vertical segment. Their 2025 paper allows edge crossings, treating each crossing as a dummy point, and requires every face to be a rectangle. Most earlier work on such tidy drawings banned crossings entirely.

The drawings live on integer grids, a classic demand in graph visualization. The authors give efficient, easy-to-code algorithms that decide whether a graph admits such a drawing and build one when possible. They vary the rules by capping vertex degree or face size, and by fixing either the outer boundary or the rotation scheme in advance. Each variant gets its own decision method.

Catalog record

CREATORPatrizio Angelini, Carla Binucci, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Fabrizio Grosso, Giacomo Ortali, Ioannis G. Tollis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01526

Browse the full library · About the Tower of Babel

Full text

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

Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces Thanks: This research was supported, in part, by MUR of Italy (PRIN Project no. 2022ME9Z78 – NextGRAAL and PRIN Project no. 2022TS4Y3N – EXPAND). The sixth author was supported by Ce.Di.Pa. - PNC Programma unitario di interventi per le aree del terremoto del 2009-2016 - Linea di intervento 1 sub-misura B4 - ”Centri di ricerca per l’innovazione” CUP J37G22000140001. Patrizio Angelini, Carla Binucci, Giuseppe Di Battista, Emilio Di Giacomo, Walter Didimo, Fabrizio Grosso, Giacomo Ortali, Ioannis G. Tollis Abstract Unit edge-length drawings, rectilinear drawings (where each edge is either a horizontal or a vertical segment), and rectangular face drawings are among the most studied subjects in Graph Drawing. However, most of the literature on these topics refers to planar graphs and planar drawings. In this paper we study drawings with all the above nice properties but that can have edge crossings; we call them Unit Edge-length Rectilinear drawings with Rectangular Faces (UER-RF drawings). We consider crossings as dummy vertices and apply the unit edge-length convention to the edge segments connecting any two (real or dummy) vertices. Note that UER-RF drawings are grid drawings (vertices are placed at distinct integer coordinates), which is another classical requirement of graph visualizations. We present several efficient and easily implementable algorithms for recognizing graphs that admit UER-RF drawings and for constructing such drawings if they exist. We consider restrictions on the degree of the vertices or on the size of the faces. For each type of restriction, we consider both the general unconstrained setting and a setting in which either the external boundary of the drawing is fixed or the rotation system of the graph is fixed as part of the input. 1 Introduction Planar graph drawings where all edges have unit length and are represented as either horizontal or vertical segments (rectilinear drawings), and where all faces are convex (i.e., rectangles), adhere to several of the most celebrated Graph Drawing aesthetics. Further, such drawings can be translated in the plane so that their vertices have integer coordinates. Motivated by these considerations, a recent paper investigated these types of planar layouts [ 2 ] . We extend the above drawing convention to non-planar drawings, considering each crossing as a “dummy” vertex and applying the unit edge-length constraint to the edge segments connecting any two vertices, either real or dummy. In this setting, we study Unit Edge-length Rectilinear drawings with Rectangular Faces ( UER-RF drawings ), i.e., rectilinear drawings in which all the edges have unit length and all the faces (including the external one) are rectangles. Examples of UER-RF drawings are presented in Figure 1 . Note that, in addition to guaranteeing edges without bends and rectangular faces, UER-RF drawings (when they exist) are typically more compact than orthogonal grid drawings computed with classical algorithms, which aim to minimize crossings and bends at the same time; for a visual comparison, see for example Figure 2 . (a) 5\times 5 (b) 5\times 5 (c) 5\times 5 Figure 1 : UER-RF drawings: with Unit Square Faces (a), with no internal degree-3 vertex (b), and in the general setting (c). All drawings occupy a 5\times 5 grid area. (a) 11\times 10 (b) 11\times 11 (c) 10\times 11 Figure 2 : The same graphs depicted in Figure 1 drawn with the topology-shape-metrics algorithm implemented in the GDToolkit library [ 6 ] . Below each drawing we report the width and the height in terms of grid units. These dimensions are at least twice those of the drawings in Figure 1 ; the three drawings have been scaled-down to fit in the same row. The problem we study is related to several challenging problems. Recognizing graphs that admit planar straight-line drawings with all edges of the same length is NP-hard [ 5 , 9 ] and, even stronger, \exists\mathbb{R} -complete [ 1 , 21 ] . Testing whether a graph is rectilinear planar is NP-hard [ 11 ] , as well as, recognizing graphs that admit unit edge-length drawings with integer coordinates is NP-complete even for trees [ 4 , 12 , 13 ] . On the other hand, recognizing planar graphs that admit rectilinear drawings with rectangular faces (with unconstrained edge lengths) can be done in polynomial time if the planar embedding is part of the input [ 20 , 22 ] ; see also [ 10 , 17 , 18 ] . Additionally, observe that UER-RF drawings are RAC drawings (for surveys see [ 3 , 7 ] ) and that non-planar drawings are intensively studied in the beyond planarity area (for surveys see [ 8 , 14 ] ). Alegría et al. [ 2 ] show that recognizing planar graphs admitting planar UER-RF drawings is feasible in polynomial time. We aim to extend this result to non-planar graphs. We study the recognition and the construction of UER-RF drawings under various conditions: when the rotation system of the vertices is part of the input, when it is not, and when the external face is part of the input or not. In our problem, an important role is played by the assignment of angles around the vertices. Requiring rectangular faces enforces 180^{\circ} angles at degree-2 vertices, and the difficulty emerges in presence of degree-3 vertices. In view of this, we present incremental restricted scenarios in which we are able to solve the problem efficiently, and then give a fixed-parameter-tractable (FPT) algorithm for the general case, parameterized by the number of degree-3 vertices. Additionally, we consider UER-RF drawings in which all faces, except the external one, are unit-area squares. We refer to these drawings as Unit Edge-length Rectilinear drawings with Unit Square Faces ( UER-USF drawings ); they have the nice feature of fully exploiting the available rows and columns; see Figure 1(a) for an example. Let G be an n -vertex graph; we present the following results: - An O(n) -time algorithm that tests whether G admits a UER-USF drawing. The algorithm can be adapted to preserve a prescribed external face ( Section 3 ). - Polynomial-time testing algorithms for UER-RF drawings in restricted scenarios ( Section 4 ). We consider drawings without internal degree-3 vertices, and drawings such that removing the external face yields a collection of paths and cycles. The complexity of these algorithms ranges from O(n) to O(n^{5}) , depending on the specific constraints on the external face and on the rotation system. - An O(3^{k}n^{4.5}) -time testing algorithm for general UER-RF drawings, where k is the number of degree-3 vertices ( Section 5 ). All our algorithms are easily implementable and can preserve a given rotation system for the vertices, if needed. If the recognition is successful, within the same time complexity of the test, they can construct the corresponding drawing. 2 Basic Definitions Let V(G) and E(G) denote the set of vertices and the set of edges of a graph G , respectively. Also, for a vertex v\in V(G) , let N(v) be the set of neighbors of v , i.e., the set of vertices adjacent to v . The value |N(v)| is the degree of v , and is denoted by \deg_{G}(v) . For a positive integer k , a graph G is a

Read the complete text