graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

, a RAC drawing of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

is a drawing in which the vertices are represented as points, the edges are represented as straight

line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

s or

polyline In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...

s, at most two edges cross at any point, and when two edges cross they do so at

right angle In geometry and trigonometry, a right angle is an angle of exactly 90 Degree (angle), degrees or radians corresponding to a quarter turn (geometry), turn. If a Line (mathematics)#Ray, ray is placed so that its endpoint is on a line and the ad ...

s 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 ,. motivated by previous user studies showing that crossings with large angles are much less harmful to the readability of drawings than shallow crossings. Even for

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s, allowing some right-angle crossings in a drawing of the graph can significantly improve measures of the drawing quality such as its

area Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape A shape or figure is a graphics, graphical representation of an obje ...

angular resolution Angular resolution describes the ability of any image-forming device such as an optical or radio telescope, a microscope, a camera, or an eye, to distinguish small details of an object, thereby making it a major determinant of image resolution. ...

Examples

The

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

''K''₅ has a RAC drawing with straight edges, but ''K''₆ does not. Every 6-vertex RAC drawing has at most 14 edges, but ''K''₆ has 15 edges, too many to have a RAC drawing. A

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

''K''_''a'',''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

, and (by

Fáry's theorem In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straigh ...

) 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 ''K''_3,3 and ''K''_3,4. A drawing of ''K''_3,4 is shown; ''K''_3,3 can be formed from it by deleting one vertex. Neither of the next two larger graphs, ''K''_4,4 and ''K''_3,5, has 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 4''n'' − 10 edges. This is tight: there exist RAC-drawable graphs with exactly 4''n'' − 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.5''n'' edges and with two bends there are at most 74.2''n'' 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 4''n'' − 10 bound on the number of edges of straight-line RAC drawings is close to the bounds of 4''n'' − 8 on the number of edges in a

1-planar graph In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural ...

, and of 4''n'' − 9 on the number of edges in a straight-line 1-planar graph. Every RAC drawing with 4''n'' − 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 4''n'' − 10 edges that do not have RAC drawings..

Computational complexity

It is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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 In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form \exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n), where the variables X_i are interpre ...

. The RAC drawing problem remains NP-hard for upward drawing of

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...

s. However, in the special case of outer-1-planar graphs, a RAC drawing can be constructed in linear time.

References

{{reflist Graph drawing