Circle graph

For the chart, see Pie chart.

A circle with five chords and the corresponding circle graph.

In graph theory, a circle graph is the intersection graph of a set of chords of a circle. 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

Spinrad (1994) 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 on general graphs have polynomial time algorithms when restricted to circle graphs. For instance, Kloks (1996) 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 with as few edges as possible that contains the given circle graph as a subgraph) may be found in O(n³) time.^[1] Tiskin (2010) has shown that a maximum clique of a circle graph can be found in O(nlog² n) time, while Nash & Gregg (2010) 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.^[2]

Chromatic number

The chords forming the 220-vertex 5-chromatic triangle-free circle graph of Ageev (1996), drawn as an arrangement of lines in the hyperbolic plane.

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.^[3] 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.^[4] In the particular case when k = 3 (that is, for triangle-free 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.^[5] 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.^[6]

Applications

Circle graphs arise in VLSI 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. ^[7] 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 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 embeddings 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.^[8]

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 of a set of intervals on a line is called the interval graph.

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

Every distance-hereditary graph is a circle graph, as is every permutation graph. Every outerplanar graph is also a circle graph.^[9]

Notes

1. ^ Kloks, Kratsch & Wong (1998).
2. ^ Keil (1993)
3. ^ Garey et al. (1980); Unger (1988).
4. ^ Gyárfás (1985); Kostochka (1988); Kostochka & Kratochvíl (1997).
5. ^ Karapetyan (1984); Gyárfás & Lehel (1985); Kostochka (1988); Ageev (1996).
6. ^ Ageev (1999).
7. ^ Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"
8. ^ Unger (1988).
9. ^ Wessel & Pöschel (1985); Unger (1988).

References

• Ageev, A. A. (1996), "A triangle-free circle graph with chromatic number 5", Discrete Math. 152 (1-3): 295–298, doi:10.1016/0012-365X(95)00349-2 .
• Ageev, A. A. (1999), "Every circle graph of girth at least 5 is 3-colourable", Discrete Math. 195 (1-3): 229–233, doi:10.1016/S0012-365X(98)00192-7 .
• Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. (1980), "The complexity of coloring circular arcs and chords", SIAM. J. on Algebraic and Discrete Methods 1 (2): 216–227, doi:10.1137/0601025 .
• Gyárfás, A. (1985), "On the chromatic number of multiple interval graphs and overlap graphs", Discrete Math. 55 (2): 161–166, doi:10.1016/0012-365X(85)90044-5 . As cited by Ageev (1996).
• Gyárfás, A.; Lehel, J. (1985), "Covering and coloring problems for relatives of intervals", Discrete Math. 55 (2): 167–180, doi:10.1016/0012-365X(85)90045-7 . As cited by Ageev (1996).
• Karapetyan, A. (1984) (in Russian), On perfect arc and chord intersection graphs, Ph.D. thesis, Inst. of Mathematics, Novosibirsk . As cited by Ageev (1996).
• Keil, J. Mark (1993), "The complexity of domination problems in circle graphs", Discrete Applied Mathematics 42 (1): 51–63, doi:10.1016/0166-218X(93)90178-Q .
• Kloks, Ton (1996), "Treewidth of Circle Graphs", Int. J. Found. Comput. Sci. 7 (2): 111–120, doi:10.1142/S0129054196000099 .
• Kloks, T.; Kratsch, D.; Wong, C. K. (1998), "Minimum fill-in on circle and circular-arc graphs", Journal of Algorithms 28 (2): 272–289, doi:10.1006/jagm.1998.0936 .
• Kostochka, A.V. (1988), "On upper bounds for the chromatic numbers of graphs" (in Russian), Trudy Instituta Mathematiki 10: 204–226 . As cited by Ageev (1996).
• Kostochka, A.V.; Kratochvíl, J. (1997), "Covering and coloring polygon-circle graphs", Discrete Math. 163 (1–3): 299–305, doi:10.1016/S0012-365X(96)00344-5 .
• Spinrad, Jeremy (1994), "Recognition of circle graphs", Journal of Algorithms 16 (2): 264–282, doi:10.1006/jagm.1994.1012 .
• Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832 .
• Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst, Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, 73, B.G. Teubner, pp. 207–210 . As cited by Unger (1988).
• Tiskin, Alexander (2010), "Fast distance multiplication of unit-Monge matrices.", Proceedings of ACM-SIAM SODA 2010, pp. 1287–1296 .
• Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters 116 (16): 630–634, doi:10.1016/j.ipl.2010.05.016 .

External links

• Circle graph, Information System on Graph Class Inclusions, http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_132.html