09-07-2026, 10:55 PM
Arc Diagram
An arc diagram is a method of drawing a graph in which all vertices are placed along a straight line and the edges are represented by semicircles or other convex curves drawn above or below that line. For directed graphs, a common convention is to use arcs above the line for one direction and below it for the opposite direction. Although the term arc diagram became popular through Martin Wattenberg’s 2002 work on visualizing repeated patterns in strings, similar graph representations date back at least to the 1960s.
Mathematically, arc diagrams are closely related to graph theory, graph drawing, planar graphs, Hamiltonian graphs, book embeddings, and crossing-number problems. Every planar graph can be represented as a crossing-free arc diagram if edges are allowed to consist of more than one semicircle. However, requiring each edge to be represented by a single semicircle imposes much stronger restrictions: such crossing-free drawings correspond to two-page book embeddings, and deciding whether a graph admits one is NP-complete. Minimizing the number of crossings is also NP-hard.
Arc diagrams also have applications well beyond pure graph drawing. They are used in information visualization, in the Farey diagram of rational numbers—where fractions $p/q$ and $r/s$ are connected when $|ps-rq|=1$—and in molecular biology for visualizing RNA, DNA, and protein structures. In RNA diagrams, for example, crossing arcs can represent pseudoknots and other aspects of molecular topology.
Key takeaways
ARTICLE
An arc diagram is a method of drawing a graph in which all vertices are placed along a straight line and the edges are represented by semicircles or other convex curves drawn above or below that line. For directed graphs, a common convention is to use arcs above the line for one direction and below it for the opposite direction. Although the term arc diagram became popular through Martin Wattenberg’s 2002 work on visualizing repeated patterns in strings, similar graph representations date back at least to the 1960s.
Mathematically, arc diagrams are closely related to graph theory, graph drawing, planar graphs, Hamiltonian graphs, book embeddings, and crossing-number problems. Every planar graph can be represented as a crossing-free arc diagram if edges are allowed to consist of more than one semicircle. However, requiring each edge to be represented by a single semicircle imposes much stronger restrictions: such crossing-free drawings correspond to two-page book embeddings, and deciding whether a graph admits one is NP-complete. Minimizing the number of crossings is also NP-hard.
Arc diagrams also have applications well beyond pure graph drawing. They are used in information visualization, in the Farey diagram of rational numbers—where fractions $p/q$ and $r/s$ are connected when $|ps-rq|=1$—and in molecular biology for visualizing RNA, DNA, and protein structures. In RNA diagrams, for example, crossing arcs can represent pseudoknots and other aspects of molecular topology.
Key takeaways
- Main mathematical area: Graph Theory / Discrete Mathematics.
- Closely related fields: Computational Geometry, Graph Algorithms and Combinatorics.
- Vertices lie on a line; edges are represented by arcs.
- Arc diagrams are useful for studying planarity, crossings, Hamiltonian cycles and book embeddings.
- Some optimization problems involving arc diagrams are NP-hard or NP-complete.
- Applications include data visualization, number theory and computational biology.
ARTICLE
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘