RAC drawing
{{Short description|Graph theory representation}}
File:RAC_drawings.svg K5 and the complete bipartite graph K3,4]]
In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when two edges cross they do so at right angles to each other. In the name of this drawing style, "RAC" stands for "right angle crossing".
The right-angle crossing style and the name "RAC drawing" for this style were both formulated by {{harvtxt|Didimo|Eades|Liotta|2009}},{{citation
| last1 = Didimo | first1 = Walter
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Liotta | first3 = Giuseppe
| contribution = Drawing graphs with right angle crossings
| doi = 10.1007/978-3-642-03367-4_19
| pages = 206–217
| series = Lecture Notes in Computer Science
| title = Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21–23, 2009. Proceedings
| volume = 5664
| year = 2009| isbn = 978-3-642-03366-7
}}. motivated by previous user studies showing that crossings with large angles are much less harmful to the readability of drawings than shallow crossings.{{citation
| last1 = Huang | first1 = Weidong
| last2 = Hong | first2 = Seok-Hee | author2-link = Seok-Hee Hong
| last3 = Eades | first3 = Peter | author3-link = Peter Eades
| contribution = Effects of crossing angles
| doi = 10.1109/PACIFICVIS.2008.4475457
| pages = 41–46
| title = IEEE Pacific Visualization Symposium (PacificVIS '08)
| year = 2008| isbn = 978-1-4244-1966-1
}}. Even for planar graphs, allowing some right-angle crossings in a drawing of the graph can significantly improve measures of the drawing quality such as its area or angular resolution.{{citation
| last = van Kreveld | first = Marc
| contribution = The quality ratio of RAC drawings and planar drawings of planar graphs
| doi = 10.1007/978-3-642-18469-7_34
| pages = 371–376
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers
| volume = 6502
| year = 2011| doi-access = free
| isbn = 978-3-642-18468-0
}}.
Examples
The complete graph K5 has a RAC drawing with straight edges, but K6 does not. Every 6-vertex RAC drawing has at most 14 edges, but K6 has 15 edges, too many to have a RAC drawing.
A complete bipartite graph Ka,b has a RAC drawing with straight edges if and only if either min(a,b) ≤ 2 or a + b ≤ 7. If min(a,b) ≤ 2, then the graph is a planar graph, and (by Fáry's theorem) every planar graph has a straight-line drawing with no crossings. Such a drawing is automatically a RAC drawing. The only two cases remaining are the graphs K3,3 and K3,4. A drawing of K3,4 is shown; K3,3 can be formed from it by deleting one vertex. Neither of the next two larger graphs, K4,4 and K3,5, has a RAC drawing.{{citation
| last1 = Didimo | first1 = Walter
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Liotta | first3 = Giuseppe
| doi = 10.1016/j.ipl.2010.05.023
| issue = 16
| journal = Information Processing Letters
| mr = 2676805
| pages = 687–691
| title = A characterization of complete bipartite RAC graphs
| volume = 110
| year = 2010}}.
Edges and bends
If an n-vertex graph (n ≥ 4) has a RAC drawing with straight edges, it can have at most 4n − 10 edges. This is tight: there exist RAC-drawable graphs with exactly 4n − 10 edges. For drawings with polyline edges, the bound on the number of edges in the graph depends on the number of bends that are allowed per edge. The graphs that have RAC drawings with one or two bends per edge have O(n) edges; more specifically, with one bend there are at most 5.5n edges{{cite arXiv |mode=cs2
| last1 = Angelini | first1 = Patrizio
| last2 = Bekos| first2 = Michael
| last3 = Förster | first3 = Henry
| last4 = Kaufmann | first4 = Michael
| eprint = 1808.10470
| title = On RAC Drawings of Graphs with one Bend per Edge
| year = 2018| class = cs.DS }} and with two bends there are at most 74.2n edges.{{citation
| last1 = Arikushi | first1 = Karin
| last2 = Fulek | first2 = Radoslav
| last3 = Keszegh | first3 = Balázs
| last4 = Morić | first4 = Filip
| last5 = Tóth | first5 = Csaba D.
| arxiv = 1001.3117
| doi = 10.1016/j.comgeo.2011.11.008 | doi-access=free
| issue = 4
| journal = Computational Geometry Theory & Applications
| mr = 2876688
| pages = 169–177
| title = Graphs that admit right angle crossing drawings
| volume = 45
| year = 2012}}. Every graph has a RAC drawing with three bends per edge.
Relation to 1-planarity
A graph is 1-planar if it has a drawing with at most one crossing per edge. Intuitively, this restriction makes it easier to cause this crossing to be at right angles, and the 4n − 10 bound on the number of edges of straight-line RAC drawings is close to the bounds of 4n − 8 on the number of edges in a 1-planar graph, and of 4n − 9 on the number of edges in a straight-line 1-planar graph. Every RAC drawing with 4n − 10 edges is 1-planar.{{citation
| last = Ackerman | first = Eyal
| doi = 10.1016/j.dam.2014.05.025
| journal = Discrete Applied Mathematics
| mr = 3223912
| pages = 104–108
| title = A note on 1-planar graphs
| volume = 175
| year = 2014| doi-access = free
}}. Additionally, every outer-1-planar graph (that is, a graph drawn with one crossing per edge with all vertices on the outer face of the drawing) has a RAC drawing.{{citation
| last1 = Dehkordi | first1 = Hooman Reisi
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| doi = 10.1142/S021819591250015X
| issue = 6
| journal = International Journal of Computational Geometry & Applications
| mr = 3042921
| pages = 543–557
| title = Every outer-1-plane graph has a right angle crossing drawing
| volume = 22
| year = 2012}}. However, there exist 1-planar graphs with 4n − 10 edges that do not have RAC drawings.{{citation
| last1 = Eades | first1 = Peter | author1-link = Peter Eades
| last2 = Liotta | first2 = Giuseppe
| doi = 10.1016/j.dam.2012.11.019
| issue = 7–8
| journal = Discrete Applied Mathematics
| mr = 3030582
| pages = 961–969
| title = Right angle crossing graphs and 1-planarity
| volume = 161
| year = 2013| doi-access = free
}}.
Computational complexity
It is NP-hard to determine whether a given graph has a RAC drawing with straight edges,{{citation
| last1 = Argyriou | first1 = Evmorfia N.
| last2 = Bekos | first2 = Michael A.
| last3 = Symvonis | first3 = Antonios
| contribution = The straight-line RAC drawing problem is NP-hard
| doi = 10.1007/978-3-642-18381-2_6
| pages = 74–85
| series = Lecture Notes in Computer Science
| title = SOFSEM 2011: 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011, Proceedings
| volume = 6543
| year = 2011| arxiv = 1009.5227| bibcode = 2011LNCS.6543...74A| isbn = 978-3-642-18380-5
}} even if the input graph is 1-planar and the output RAC drawing must be 1-planar as well.{{citation
| last1 = Bekos | first1 = Michael A.
| last2 = Didimo | first2 = Walter
| last3 = Liotta | first3 = Giuseppe
| last4 = Mehrabi | first4 = Saeed
| last5 = Montecchiani | first5 = Fabrizio
| title = On RAC drawings of 1-planar graphs
| doi = 10.1016/j.tcs.2017.05.039
| pages = 48–57
| journal = Theoretical Computer Science
| volume = 689
| year = 2017| arxiv = 1608.08418}} More specifically, RAC drawing is complete for the existential theory of the reals.{{citation|first=Marcus|last=Schaefer|year=2021|contribution=RAC-drawability is -complete|arxiv=2107.11663|title=Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)}} The RAC drawing problem remains NP-hard for upward drawing of directed acyclic graphs.{{citation
| last1 = Angelini | first1 = Patrizio
| last2 = Cittadini | first2 = Luca
| last3 = Di Battista | first3 = Giuseppe
| last4 = Didimo | first4 = Walter
| last5 = Frati | first5 = Fabrizio
| last6 = Kaufmann | first6 = Michael
| last7 = Symvonis | first7 = Antonios
| contribution = On the perspectives opened by right angle crossing drawings
| doi = 10.1007/978-3-642-11805-0_5
| pages = 21–32
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22–25, 2009, Revised Papers
| volume = 5849
| year = 2010| doi-access = free
| isbn = 978-3-642-11804-3
}}. However, in the special case of outer-1-planar graphs, a RAC drawing can be constructed in linear time.{{citation|last1=Auer|first1=Christopher|last2=Bachmaier|first2=Christian|last3=Brandenburg|first3=Franz J.|last4=Hanauer|first4=Kathrin|last5=Gleißner|first5=Andreas|last6=Neuwirth|first6=Daniel|last7=Reislhuber|first7=Josef |title=Graph Drawing |chapter=Recognizing Outer 1-Planar Graphs in Linear Time |series=Lecture Notes in Computer Science |date=2013|volume=8284|pages=107–118|doi=10.1007/978-3-319-03841-4_10|isbn=978-3-319-03840-7 }}