In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a circle graph is the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

 of a set of chords

Chord (geometry)

A chord of a circle is a geometric line segment whose endpoints both lie on the circumference of the circle.A secant or a secant line is the line extension of a chord. More generally, a chord is a line segment joining two points on any curve, such as but not limited to an ellipse...

 of a circle

Circle

A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....

. That is, it is an undirected graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

Algorithmic complexity

gives an O(n²)-time algorithm that tests whether a given n-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it.

A number of other problems that are NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

 on general graphs have polynomial time algorithms when restricted to circle graphs. For instance, showed that the treewidth of a circle graph can be determined, and an optimal tree decomposition constructed, in O(n³) time. Additionally, a minimum fill-in (that is, a chordal graph

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

 with as few edges as possible that contains the given circle graph as a subgraph) may be found in O(n³) time.
has shown that a maximum clique of a circle graph can be found in O(nlog² n) time, while
have shown that a maximum independent set of an unweighted circle graph can be found in O(nmin{d, α}) time, where d is a parameter of the graph known as its density, and α is the independence number of the circle graph.

However, there are also problems that remain NP-complete when restricted to circle graphs. These include the minimum dominating set, minimum connected dominating set, and minimum total dominating set problems.

Chromatic number

The chromatic number of a circle graph is the minimum number of colors that can be used to color its chords so that no two crossing chords have the same color. Since it is possible to form circle graphs in which arbitrarily large sets of chords all cross each other, the chromatic number of a circle graph may be arbitrarily large, and determining the chromatic number of a circle graph is NP-complete. However, several authors have investigated problems of coloring restricted subclasses of circle graphs with few colors. In particular, for circle graphs in which no sets of k or more chords all cross each other, it is possible to color the graph with as few as 2^k + 6 colors. In the particular case when k = 3 (that is, for triangle-free

Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...

 circle graphs) the chromatic number is at most five, and this is tight: all triangle-free circle graphs may be colored with five colors, and there exist triangle-free circle graphs that require five colors. If a circle graph has girth at least five (that is, it is triangle-free and has no four-vertex cycles) it can be colored with at most three colors.

Applications

Circle graphs arise in VLSI physical design

Physical design

Physical design can refer to*Physical database design - see also Physical data model*Physical design...

 as an abstract representation for a special case for wire routing, known as "two-terminal switchbox routing". In this case the routing area is a rectangle, all nets are two-terminal, and the terminals are placed on the perimeter of the rectangle. It is easily seen that the intersection graph of these nets is a circle graph. Among the goals of wire routing step is to ensure that different nets stay electrically disconnected, and their potential intersecting parts must be laid out

Integrated circuit layout

Integrated circuit layout, also known IC layout, IC mask layout, or mask design, is the representation of an integrated circuit in terms of planar geometric shapes which correspond to the patterns of metal, oxide, or semiconductor layers that make up the components of the integrated circuit.When...

 in different conducting layers. Therefore circle graphs capture various aspects of this routing problem.

Colorings of circle graphs may also be used to find book embedding

Book embedding

In graph theory, book embedding is a generalization of planar embedding to nonplanar surfaces in the form of a book, a collection of pages joined together at the spine of the book . The vertices of the graph are embedded on the spine, and each edge must lie in one of the pages...

s of arbitrary graphs: if the vertices of a given graph G are arranged on a circle, with the edges of G forming chords of the circle, then the intersection graph of these chords is a circle graph and colorings of this circle graph are equivalent to book embeddings that respect the given circular layout.

Related graph classes

A graph is a circle graph if and only if it is the overlap graph of a set of intervals on a line. This is a graph in which the vertices correspond to the intervals, and two vertices are connected by an edge if the two intervals overlap, with neither containing the other.

The intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

 of a set of intervals on a line is called the interval graph

Interval graph

In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...

.

String graph

String graph

In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the...

s, the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

s of curves in the plane, include circle graphs as a special case.

Every distance-hereditary graph

Distance-hereditary graph

In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...

 is a circle graph, as is every permutation graph

Permutation graph

In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...

. Every outerplanar graph

Outerplanar graph

In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...

is also a circle graph.