2026-07-21T14:19:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18662 2024-03-06T11:02:23Z ddc:004 open_access

Axis-Parallel Right Angle Crossing Graphs Angelini, Patrizio Bekos, Michael A. Katheder, Julia Kaufmann, Michael Pfister, Maximilian Ueckerdt, Torsten Graph drawing RAC graphs Graph drawing algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patrizio Angelini and Michael A. Bekos and Julia Katheder and Michael Kaufmann and Maximilian Pfister and Torsten Ueckerdt 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.9 urn:nbn:de:0030-drops-186623 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode