Loading...
Axis-Parallel Right Angle Crossing Graphs
Angelini, Patrizio
Bekos, Michael A. Katheder, Julia Kaufmann, Michael Pfister, Maximilian Ueckerdt, Torsten
Bekos, Michael A.
Katheder, Julia
Kaufmann, Michael
Pfister, Maximilian
Ueckerdt, Torsten
Citations
Altmetric:
Abstract
A RAC graph is one admitting a RAC drawing, that is, a polyline drawing in which each crossing occurs at a right angle. Originally motivated by psychological studies on readability of graph layouts, RAC graphs form one of the most prominent graph classes in beyond planarity. In this work, we study a subclass of RAC graphs, called axis-parallel RAC (or apRAC, for short), that restricts the crossings to pairs of axis-parallel edge-segments. apRAC drawings combine the readability of planar drawings with the clarity of (non-planar) orthogonal drawings. We consider these graphs both with and without bends. Our contribution is as follows: (i) We study inclusion relationships between apRAC and traditional RAC graphs. (ii) We establish bounds on the edge density of apRAC graphs. (iii) We show that every graph with maximum degree 8 is 2-bend apRAC and give a linear time drawing algorithm. Some of our results on apRAC graphs also improve the state of the art for general RAC graphs. We conclude our work with a list of open questions and a discussion of a natural generalization of the apRAC model.
Description
Date
2023
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Graph drawing, RAC graphs, Graph drawing algorithms
Citation
Patrizio Angelini, Michael A. Bekos, Julia Katheder, Michael Kaufmann, Maximilian Pfister, and Torsten Ueckerdt. Axis-Parallel Right Angle Crossing Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs) 274(9):1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)