Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Arc diagram
An arc diagram is a style of graph drawing, in which the vertices of a graph are placed along a line in the Euclidean plane and edges are drawn using semicircles or other convex curves above or below the line. These drawings are also called linear embeddings or circuit diagrams.
Applications of arc diagrams include information visualization, the Farey diagram of number-theoretic connections between rational numbers, and diagrams representing RNA secondary structure in which the crossings of the diagram represent pseudoknots in the structure.
In an arc diagram, the vertices of a graph are arranged along a line in the Euclidean plane. The edges are drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles. In some cases, line segments of the line itself are also allowed as edges, as long as they connect only vertices that are consecutive along the line. Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.
For drawings of directed graphs, a common convention is to draw each arc in a clockwise direction, so that arcs that are directed from an earlier to a later vertex in the sequence are drawn above the vertex line, and arcs directed from a later to an earlier vertex are drawn below the line.
The use of the phrase "arc diagram" for this kind of drawing follows the use of a similar type of diagram by Wattenberg (2002) to visualize the repetition patterns in strings, by using arcs to connect pairs of equal substrings. However, this style of graph drawing is much older than its name, dating back at least to the work of Saaty (1964) and Nicholson (1968), who used arc diagrams to study crossing numbers of graphs.
Arc diagrams are also called linear embeddings. In their application to the circuit topology of RNA secondary structure, they are called circuit diagrams.
As Nicholson (1968) observed, every drawing of a graph in the plane may be deformed into an arc diagram, without changing its number of crossings. In particular, every planar graph has a planar arc diagram. However, this embedding may need to use more than one semicircle for some of its edges.
If a graph is drawn without crossings using an arc diagram in which each edge is a single semicircle, then the drawing is a two-page book embedding. This kind of drawing is only possible for the subhamiltonian graphs, a proper subset of the planar graphs. For instance, a maximal planar graph has such an embedding if and only if it contains a Hamiltonian cycle. Therefore, a non-Hamiltonian maximal planar graph such as the Goldner–Harary graph cannot have a planar embedding with one semicircle per edge. Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is NP-complete.
Hub AI
Arc diagram AI simulator
(@Arc diagram_simulator)
Arc diagram
An arc diagram is a style of graph drawing, in which the vertices of a graph are placed along a line in the Euclidean plane and edges are drawn using semicircles or other convex curves above or below the line. These drawings are also called linear embeddings or circuit diagrams.
Applications of arc diagrams include information visualization, the Farey diagram of number-theoretic connections between rational numbers, and diagrams representing RNA secondary structure in which the crossings of the diagram represent pseudoknots in the structure.
In an arc diagram, the vertices of a graph are arranged along a line in the Euclidean plane. The edges are drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles. In some cases, line segments of the line itself are also allowed as edges, as long as they connect only vertices that are consecutive along the line. Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.
For drawings of directed graphs, a common convention is to draw each arc in a clockwise direction, so that arcs that are directed from an earlier to a later vertex in the sequence are drawn above the vertex line, and arcs directed from a later to an earlier vertex are drawn below the line.
The use of the phrase "arc diagram" for this kind of drawing follows the use of a similar type of diagram by Wattenberg (2002) to visualize the repetition patterns in strings, by using arcs to connect pairs of equal substrings. However, this style of graph drawing is much older than its name, dating back at least to the work of Saaty (1964) and Nicholson (1968), who used arc diagrams to study crossing numbers of graphs.
Arc diagrams are also called linear embeddings. In their application to the circuit topology of RNA secondary structure, they are called circuit diagrams.
As Nicholson (1968) observed, every drawing of a graph in the plane may be deformed into an arc diagram, without changing its number of crossings. In particular, every planar graph has a planar arc diagram. However, this embedding may need to use more than one semicircle for some of its edges.
If a graph is drawn without crossings using an arc diagram in which each edge is a single semicircle, then the drawing is a two-page book embedding. This kind of drawing is only possible for the subhamiltonian graphs, a proper subset of the planar graphs. For instance, a maximal planar graph has such an embedding if and only if it contains a Hamiltonian cycle. Therefore, a non-Hamiltonian maximal planar graph such as the Goldner–Harary graph cannot have a planar embedding with one semicircle per edge. Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is NP-complete.