RAC drawing

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. ==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. and with two bends there are at most 74.2n edges. 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. 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. However, there exist 1-planar graphs with 4n − 10 edges that do not have RAC drawings. ==Computational complexity==

It is NP-hard to determine whether a given graph has a RAC drawing with straight edges, even if the input graph is 1-planar and the output RAC drawing must be 1-planar as well. More specifically, RAC drawing is complete for the existential theory of the reals. The RAC drawing problem remains NP-hard for upward drawing of directed acyclic graphs. However, in the special case of outer-1-planar graphs, a RAC drawing can be constructed in linear time. ==References==