2024/11/26 by Förster, Julia Katheder, Katheder, Julia +2
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2411.17565
openalex publication_date 2024/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An outer-RAC drawing of a graph is a straight-line drawing where all vertices are incident to the outer cell and all edge crossings occur at a right angle. If additionally, all crossing edges are either horizontal or vertical, we call the drawing outer-apRAC (ap for axis-parallel). A graph is outer-(ap)RAC if it admits an outer-(ap)RAC drawing. We investigate the class of outer-(ap)RAC graphs. We show that the outer-RAC graphs are a proper subset of~the planar graphs with at most 2.5n-4 edges where n is the number of vertices. This density bound is tight, even for outer-apRAC graphs. Moreover, we provide an SPQR-tree based linear-time algorithm which computes an outer-RAC drawing for every given series-parallel graph of maximum degree four. As a complementing result, we present planar graphs of maximum degree four and series-parallel graphs of maximum degree five that are not outer-RAC. Finally, for series-parallel graphs of maximum degree three we show how to compute an outer-apRAC drawing in linear time.