science

RAC drawing

RAC drawing is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand RAC drawing rather than just read about it. In short: 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".

Key takeaways

RAC drawing belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect RAC drawing to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of RAC drawing from memory before moving on to harder problems.

Reference excerpt

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 Didimo, Eades & Liotta (2009), 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 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.

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.

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 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

Illustrations

Worked examples

Example 1 — a first encounter with RAC drawing

Start with the simplest possible case. Write down what RAC drawing claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to RAC drawing before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about RAC drawing ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of RAC drawing

In research: RAC drawing appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses RAC drawing in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: RAC drawing is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph drawing, NP-complete problems, so understanding it makes those chapters shorter.
In everyday life: Look for RAC drawing outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “RAC drawing” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study RAC drawing in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what RAC drawing means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain RAC drawing out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is RAC drawing in simple terms?

Why does RAC drawing matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study RAC drawing?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on RAC drawing.