Arc Diagram
   HOME

TheInfoList



OR:

An arc diagram is a style of
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 ...
, in which the vertices of a graph are placed along a line in the
Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
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 Data and information visualization (data viz/vis or info viz/vis) is the practice of designing and creating Graphics, graphic or visual Representation (arts), representations of a large amount of complex quantitative and qualitative data and i ...
, the
Farey diagram In mathematics, the Farey sequence of order ''n'' is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction, which have denominators less than or equal to ''n'', arranged in order of increasing size. Wi ...
of number-theoretic connections between
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...
s, and diagrams representing RNA secondary structure in which the crossings of the diagram represent
pseudoknot __NOTOC__ A pseudoknot is a nucleic acid secondary structure containing at least two stem-loop structures in which half of one stem is intercalated between the two halves of another stem. The pseudoknot was first recognized in the turnip yellow ...
s in the structure.


Description

In an arc diagram, the vertices of a graph are arranged along a line in the
Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
. The edges are drawn as
semicircle In mathematics (and more specifically geometry), a semicircle is a one-dimensional locus of points that forms half of a circle. It is a circular arc that measures 180° (equivalently, radians, or a half-turn). It only has one line of symmetr ...
s 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.


History and nomenclature

The use of the phrase "arc diagram" for this kind of drawing follows the use of a similar type of diagram by 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 and , who used arc diagrams to study crossing numbers of graphs. Arc diagrams are also called ''linear embeddings''. In their application to the
circuit topology The circuit topology of a folded linear polymer refers to the arrangement of its intra-molecular contacts. Examples of linear polymers with intra-molecular contacts are nucleic acids and proteins. Proteins fold via the formation of contacts of v ...
of RNA secondary structure, they are called ''circuit diagrams''.


Planar graphs

As 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 In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
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 In graph theory, a book embedding is a generalization of planar graph, planar embedding of a Graph (discrete mathematics), graph to embeddings in a ''book'', a collection of half-planes all having the same Line (geometry), line as their boundary ...
. This kind of drawing is only possible for the
subhamiltonian graph In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.. Definition A graph ''G'' is subhamiltonian if ''G'' is a subgraph of another graph aug(''G'') on the same vertex set, such that aug(''G'') is ...
s, a proper subset of the planar graphs. For instance, a
maximal 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 cro ...
has such an embedding if and only if it contains a
Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
. Therefore, a non-Hamiltonian maximal planar graph such as the
Goldner–Harary graph In the mathematics, mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after Anita M. Goldner and Frank Harary, who proved in 1975 that it was the smallest Hamilt ...
cannot have a planar embedding with one semicircle per edge.As show, this is the smallest non-Hamiltonian maximal planar graph. The implication that it has no two-page book embedding is stated by . Testing whether a given graph has a crossing-free arc diagram of this type (or equivalently, whether it has pagenumber two) is
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
. However, every planar graph has an arc diagram in which each edge is drawn as a
biarc A biarc is a smooth curve formed from two circular arcs. In order to make the biarc smooth (Geometric continuity, ''G''1 continuous), the two arcs should have the same tangent at the connecting point where they meet. Biarcs are commonly used in ge ...
with at most two semicircles. More strongly, every ''st''-planar directed graph (a planar
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 ...
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. For undirected planar graphs, one way to construct an arc diagram with at most two semicircles per edge is to subdivide the graph and add extra edges so that the resulting graph has a
Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
(and so that each edge is subdivided at most once), and to use the ordering of the vertices on the Hamiltonian cycle as the ordering along the line. In a planar graph with n vertices, at most n/2 biarcs are needed.


Minimizing crossings

Because it is NP-complete to test whether a given graph has an arc diagram with one semicircle per edge and no crossings, it is also
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
to find an arc diagram of this type that minimizes the number of crossings. This crossing minimization problem remains NP-hard, for non-planar graphs, even if the ordering of the vertices along the line is fixed. 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 In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case ...
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. Additionally, in the fixed-ordering case, a crossing-minimizing embedding may be approximated by solving a
maximum cut In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets and , such that the number of edges between and is as large as possible. ...
problem in an auxiliary graph that represents the semicircles and their potential crossings (or equivalently, by approximating the MAX2SAT version of the 2-satisfiability instance). , , and discuss heuristics for finding arc diagrams with few crossings.


Applications

For applications in
information visualization Data and information visualization (data viz/vis or info viz/vis) is the practice of designing and creating Graphics, graphic or visual Representation (arts), representations of a large amount of complex quantitative and qualitative data and i ...
, 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. Arc diagrams were used by to visualize the
state diagram A state diagram is used in computer science and related fields to describe the behavior of systems. State diagrams require that the system is composed of a finite number of states. Sometimes, this is indeed the case, while at other times this i ...
of a
shift register A shift register is a type of digital circuit using a cascade of flip-flop (electronics), flip-flops where the output of one flip-flop is connected to the input of the next. They share a single clock signal, which causes the data stored in the syst ...
, by to show that the crossing number of every graph is lower-bounded by a combination of its cutwidth and vertex degrees, by to visualize interactions between
Bluetooth Bluetooth is a short-range wireless technology standard that is used for exchanging data between fixed and mobile devices over short distances and building personal area networks (PANs). In the most widely used mode, transmission power is li ...
devices, and by to visualize the yardage of plays in a game of
American football American football, referred to simply as football in the United States and Canada and also known as gridiron football, is a team sport played by two teams of eleven players on a rectangular American football field, field with goalposts at e ...
. Additional applications of this visualization technique are surveyed by . The
Farey diagram In mathematics, the Farey sequence of order ''n'' is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction, which have denominators less than or equal to ''n'', arranged in order of increasing size. Wi ...
of a set of
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...
s is a structure that may be represented geometrically as an arc diagram. In this form it has a vertex for each number, placed on the
number line A number line is a graphical representation of a straight line that serves as spatial representation of numbers, usually graduated like a ruler with a particular origin point representing the number zero and evenly spaced marks in either dire ...
, and a semicircular edge above the line connecting pairs of numbers p/q and r/s (in simplest terms) for which , ps-rq, =1. The semicircles of the diagram may be thought of as lines in the
Poincaré half-plane model In non-Euclidean geometry, the Poincaré half-plane model is a way of representing the hyperbolic plane using points in the familiar Euclidean plane. Specifically, each point in the hyperbolic plane is represented using a Euclidean point with co ...
of the
hyperbolic plane In mathematics, hyperbolic geometry (also called Lobachevskian geometry or Bolyai– Lobachevskian geometry) is a non-Euclidean geometry. The parallel postulate of Euclidean geometry is replaced with: :For any given line ''R'' and point ''P' ...
, with the vertices placed at infinite points on the boundary line of this model. 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. The Farey diagram of any set of rational numbers is a planar graph, and the Farey diagram of the set of all rational numbers forms a
tessellation A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety ...
of the hyperbolic plane by
ideal triangle In hyperbolic geometry an ideal triangle is a hyperbolic triangle whose three vertices all are ideal points. Ideal triangles are also sometimes called ''triply asymptotic triangles'' or ''trebly asymptotic triangles''. The vertices are sometime ...
s. Arc diagrams or circuit diagrams are commonly used in studying folded biopolymers such as proteins and
nucleic acid Nucleic acids are large biomolecules that are crucial in all cells and viruses. They are composed of nucleotides, which are the monomer components: a pentose, 5-carbon sugar, a phosphate group and a nitrogenous base. The two main classes of nuclei ...
s (DNAs, RNAs). 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. The theoretical framework of
circuit topology The circuit topology of a folded linear polymer refers to the arrangement of its intra-molecular contacts. Examples of linear polymers with intra-molecular contacts are nucleic acids and proteins. Proteins fold via the formation of contacts of v ...
is then typically applied to extract local and global topological information, which can in turn be related to biological function of the folded molecules. When arcs do not cross, the arrangement of the two arcs will be either parallel (P) or series (S). When there are crossings, the crossings represent what is often called as X arrangement in circuit topology. The statistics of P, S, and X can be used to learn about folding kinetics of these polymers.


Notes


References

*. * *. *. *. * *. *. *. *. *. *. *. *; see Section 2.4, "Farey diagrams and continued fractions" *. *. See also the same journal 6(2):33 (1975) and 8:104-106 (1977). Reference fro
listing of Harary's publications
*. *. *. *. * *. *. * *. * *. *. *. {{refend Graph drawing