Outer-(ap)RAC Graphs
摘要
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.