Drawing graphs with circular arcs and right-angle crossings. (English) Zbl 07759289
Albers, Susanne (ed.), 17th Scandinavian symposium and workshops on algorithm theory, SWAT 2020, Tórshavn, Faroe Islands, June 22–24, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 162, Article 21, 14 p. (2020).
Summary: In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with \(n\) vertices has at most \(4n-10\) edges.
We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with \(n\) vertices has at most \(14n-12\) edges and that there are \(n\)-vertex arc-RAC graphs with \(4.5n -(\sqrt{n})\) edges.
For the entire collection see [Zbl 1436.68009].
We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with \(n\) vertices has at most \(14n-12\) edges and that there are \(n\)-vertex arc-RAC graphs with \(4.5n -(\sqrt{n})\) edges.
For the entire collection see [Zbl 1436.68009].
MSC:
| 68Wxx | Algorithms in computer science |
