On RAC drawings of graphs with one bend per edge
Angelini, Patrizio
Bekos, Michael A. Förster, Henry Kaufmann, Michael
Bekos, Michael A.
Förster, Henry
Kaufmann, Michael
Citations
Altmetric:
Abstract
A k-bend right-angle-crossing drawing (or k-bend RAC drawing, for short) of a graph is a polyline drawing where each edge has at most k bends and the angles formed at the crossing points of the edges are . Accordingly, a graph that admits a k-bend RAC drawing is referred to as k-bend right-angle-crossing graph (or k-bend RAC, for short); a 0-bend RAC graph is also called a straight-line RAC graph. In this paper, we close the gap between the upper bound and the lower bound on the maximum edge-density of 1-bend RAC graphs. We show that an n-vertex 1-bend RAC graph cannot have more than edges. This bound is asymptotically tight, as we show that there exist infinitely many n-vertex 1-bend RAC graphs whose density matches the upper bound up to a constant. Our results improve both the previously known best upper bound of edges and the corresponding lower bound of edges by Arikushi et al. (2012) [9]. Finally, we consider simple 1-bend RAC drawings, that is, drawings in which each pair of edges shares at most one point (crossing or endpoint). In this setting, we provide an upper bound of and a lower bound of edges for n-vertex graphs that admit simple 1-bend RAC drawings, which shows that requiring simplicity is indeed a restriction.
Description
Date
2020
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Graph algorithms, 1-bend drawings, RAC graphs, Edge-density
Citation
Angelini, Patrizio, Michael A. Bekos, Henry Förster, and Michael Kaufmann. “On RAC Drawings of Graphs with One Bend per Edge.” Theoretical Computer Science 828–829 (August): 42–54. 2020.
ISBN
License
Attribution-NonCommercial-NoDerivatives 4.0 International