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, with edges being drawn as semicircles in one or both of the two halfplanes bounded by the line, or as smooth curves formed by sequences of semicircles.

Variations of this drawing style in which the semicircles are replaced by convex curves of some other type are also commonly called arc diagrams.

[3] Heer, Bostock & Ogievetsky (2010) write that arc diagrams "may not convey the overall structure of the graph as effectively as a two-dimensional layout", but that their layout makes it easy to display multivariate data associated with the vertices of the graph.

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.

Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is NP-complete.

More strongly, every st-planar directed graph (a planar directed acyclic graph with a single source and a single sink, both on the outer face) has an arc diagram in which every edge forms a monotonic curve, with these curves all consistently oriented from one end of the vertex line towards the other.

This crossing minimization problem remains NP-hard, for non-planar graphs, even if the ordering of the vertices along the line is fixed.

[2] However, in the fixed-ordering case, an embedding without crossings (if one exists) may be found in polynomial time by translating the problem into a 2-satisfiability problem, in which the variables represent the placement of each arc and the constraints prevent crossing arcs from being placed on the same side of the vertex line.

This clockwise orientation convention was developed as part of a different graph drawing style by Fekete et al. (2003), and applied to arc diagrams by Pretorius & van Wijk (2007).

The Poincaré half-plane model has an infinite point that is not represented as point on the boundary line, the shared endpoint of all vertical rays in the model, and this may be represented by the "fraction" 1/0 (undefined as a number), with the same rule for determining its adjacencies.

Biopolymers are typically represented by their primary monomer sequence along the line of the diagrams, and with arcs above the line representing bonds between monomers (e.g., amino acids in proteins or bases in RNA or DNA) that are adjacent in the physical structure of the polymer despite being nonadjacent in the sequence order.

[13] Arc diagrams were used by Brandes (1999) to visualize the state diagram of a shift register, by Djidjev & Vrt'o (2002) to show that the crossing number of every graph is lower-bounded by a combination of its cutwidth and vertex degrees, by Byrne et al. (2007) to visualize interactions between Bluetooth devices, and by Owens & Jankun-Kelly (2013) to visualize the yardage of plays in a game of American football.