Editing Circle graph

{{Short description|Intersection graph of a chord diagram}}
{{For|the chart|Pie chart}}
{{For|other diagrams|Circle diagram|Smith chart|Nyquist plot}}
[[Image:Circle graph and circle model.svg|thumb|175px|A circle with five chords and the corresponding circle graph.]]
In [[graph theory]], a '''circle graph''' is  the [[intersection graph]] of a [[Chord diagram (mathematics)|chord diagram]]. That is, it is an [[undirected graph]] whose vertices can be associated with a finite system of [[Chord (geometry)|chords]] of a [[circle]] such that two vertices are adjacent if and only if the corresponding chords cross each other.

==Algorithmic complexity==
After earlier [[polynomial time]] algorithms,<ref>{{harvtxt|Gabor|Supowit|Hsu|1989}}; {{harvtxt|Spinrad|1994}}</ref> {{harvtxt|Gioan|Paul|Tedder|Corneil|2013}} presented an algorithm for recognizing circle graphs in near-linear time. Their method is slower than linear by a factor of the [[inverse Ackermann function]], and is based on [[lexicographic breadth-first search]]. The running time comes from a method for maintaining the [[split decomposition]] of a graph incrementally, as vertices are added, used as a subroutine in the algorithm.{{sfnp|Gioan|Paul|Tedder|Corneil|2013}}

A number of other problems that are [[NP-complete]] on general graphs have polynomial time algorithms when restricted to circle graphs.  For instance, {{harvtxt|Kloks|1996}} showed that the [[treewidth]] of a circle graph can be determined, and an optimal tree decomposition constructed, in O(''n''<sup>3</sup>) 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''<sup>3</sup>) time.<ref>{{harvtxt|Kloks|Kratsch|Wong|1998}}.</ref> 
{{harvtxt|Tiskin|2010}} has shown that a [[maximum clique]] of a circle graph can be found in O(''n'' log<sup>2</sup> ''n'') time, while
{{harvtxt|Nash|Gregg|2010}} have shown that a [[maximum independent set]] of an unweighted circle graph can be found in O(''n'' min{''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.<ref>{{harvtxt|Keil|1993}}</ref>

==Chromatic number==
[[File:Ageev 5X circle graph.svg|thumb|left|300px|The chords forming the 220-vertex 5-chromatic triangle-free circle graph of {{harvtxt|Ageev|1996}}, drawn as an [[arrangement of lines]] in the 
[[Hyperbolic space|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.{{sfnp|Garey|Johnson|Miller|Papadimitriou|1980}} It remains NP-complete to test whether a circle graph can be colored by four colors.{{sfnp|Unger|1988}} {{harvtxt|Unger|1992}} claimed that finding a coloring with three colors may be done in [[polynomial time]] but his writeup of this result omits many details.{{sfnp|Unger|1992}}

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 <math>7k^2</math> colors. One way of stating this is that the circle graphs are [[χ-bounded|<math>\chi</math>-bounded]].<ref>{{harvtxt|Davies|McCarty|2021}}. For earlier bounds see {{harvtxt|Černý|2007}}, {{harvtxt|Gyárfás|1985}}, {{harvtxt|Kostochka|1988}}, and {{harvtxt|Kostochka|Kratochvíl|1997}}.</ref> In the particular case when ''k''&nbsp;=&nbsp;3 (that is, for [[triangle-free graph|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.<ref>See {{harvtxt|Kostochka|1988}} for the upper bound, and {{harvtxt|Ageev|1996}} for the matching lower bound. {{harvtxt|Karapetyan|1984}} and {{harvtxt|Gyárfás|Lehel|1985}} give earlier weaker bounds on the same problem.</ref> If a circle graph has [[girth (graph theory)|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.<ref>{{harvtxt|Ageev|1999}}.</ref> The problem of coloring triangle-free squaregraphs is equivalent to the problem of representing [[squaregraph]]s as isometric subgraphs of [[Cartesian product of graphs|Cartesian products]] of [[Tree (graph theory)|trees]]; in this correspondence, the number of colors in the coloring corresponds to the number of trees in the product representation.{{sfnp|Bandelt|Chepoi|Eppstein|2010}}

==Applications==
Circle graphs arise in [[VLSI]] [[Physical design (electronics)|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.<ref>Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"</ref>  Among the goals of wire routing step is to ensure that different nets stay electrically disconnected, and  their potential intersecting parts must be [[integrated circuit layout|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 embedding]]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. In this equivalence, the number of colors in the coloring corresponds to the number of pages in the book embedding.{{sfnp|Unger|1988}}

==Related graph classes==
[[File:Overlapgraph.svg|thumb|An interval system with five intervals and the corresponding overlap graph.]]
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 graph]]s, the [[intersection graph]]s 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]] and every [[indifference graph]]. Every [[outerplanar graph]] is also a circle graph.<ref>{{harvtxt|Wessel|Pöschel|1985}}; {{harvtxt|Unger|1988}}.</ref>

The circle graphs are generalized by the [[polygon-circle graph]]s, intersection graphs of polygons all inscribed in the same circle.<ref>{{citation
 | title = Circle graph
 | work = Information System on Graph Classes and their Inclusions 
 | url = http://www.graphclasses.org/classes/gc_132.html}}</ref>

==Notes==
{{reflist|30em}}

==References==
{{refbegin|30em}}
*{{citation
 | last = Ageev | first = A. A.
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 295–298
 | issue = 1–3
 | title = A triangle-free circle graph with chromatic number 5
 | volume = 152
 | year = 1996
 | doi = 10.1016/0012-365X(95)00349-2| doi-access = free
 }}.
*{{citation
 | last = Ageev | first = A. A.
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 229–233
 | issue = 1–3
 | title = Every circle graph of girth at least 5 is 3-colourable
 | volume = 195
 | year = 1999
 | doi = 10.1016/S0012-365X(98)00192-7| doi-access = free
 }}.
*{{citation|title=Combinatorics and geometry of finite and infinite squaregraphs|first1=H.-J.|last1=Bandelt|first2=V.|last2=Chepoi|first3=D.|last3=Eppstein|author3-link=David Eppstein|arxiv=0905.4537|journal=[[SIAM Journal on Discrete Mathematics]]|volume=24|issue=4|pages=1399–1440|year=2010|doi=10.1137/090760301|s2cid=10788524 }}.
*{{citation
 | last = Černý | first = Jakub
 | doi = 10.1016/j.endm.2007.07.072
 | journal = Electronic Notes in Discrete Mathematics
 | pages = 357–361
 | title = Coloring circle graphs
 | volume = 29
 | year = 2007}}.
*{{citation
 | last1 = Davies | first1 = James
 | last2 = McCarty | first2 = Rose
 | arxiv = 1905.11578
 | doi = 10.1112/blms.12447
 | issue = 3
 | journal = [[Bulletin of the London Mathematical Society]]
 | mr = 4275079
 | pages = 673–679
 | title = Circle graphs are quadratically χ-bounded
 | volume = 53
 | year = 2021| s2cid = 167217723
 }}.
*{{citation
 | last1 = Gabor | first1 = Csaba P.
 | last2 = Supowit | first2 = Kenneth J.
 | last3 = Hsu | first3 = Wen-Lian
 | date = July 1989
 | doi = 10.1145/65950.65951
 | issue = 3
 | journal = Journal of the ACM
 | pages = 435–473
 | title = Recognizing circle graphs in polynomial time
 | volume = 36| doi-access = free
 }}
*{{citation
 | last1 = Garey | first1 = M. R. | author1-link = Michael R. Garey
 | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
 | last3 = Miller | first3 = G. L. | author3-link = Gary Miller (professor)
 | last4 = Papadimitriou | first4 = C. | author4-link = Christos Papadimitriou
 | doi = 10.1137/0601025
 | issue = 2
 | journal = SIAM Journal on Algebraic and Discrete Methods
 | pages = 216–227
 | title = The complexity of coloring circular arcs and chords
 | volume = 1
 | year = 1980}}
*{{citation
 | last1 = Gioan | first1 = Emeric
 | last2 = Paul | first2 = Christophe
 | last3 = Tedder | first3 = Marc
 | last4 = Corneil | first4 = Derek | author4-link = Derek Corneil
 | date = March 2013
 | doi = 10.1007/s00453-013-9745-8
 | issue = 4
 | journal = Algorithmica
 | pages = 759–788
 | title = Practical and efficient circle graph recognition
 | volume = 69| arxiv = 1104.3284
 }}
*{{citation
 | last = Gyárfás | first = A. | authorlink = András Gyárfás
 | doi = 10.1016/0012-365X(85)90044-5
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 161–166
 | title = On the chromatic number of multiple interval graphs and overlap graphs
 | volume = 55
 | issue = 2
 | year = 1985| doi-access = free
 }}. As cited by {{harvtxt|Ageev|1996}}.
*{{citation
 | last1 = Gyárfás | first1 = A. | author1-link = András Gyárfás
 | last2 = Lehel | first2 = J.
 | doi = 10.1016/0012-365X(85)90045-7
 | issue = 2
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | title = Covering and coloring problems for relatives of intervals
 | volume = 55
 | year = 1985
 | pages = 167–180| doi-access = free
 }}. As cited by {{harvtxt|Ageev|1996}}.
*{{citation
 | last = Karapetyan | first = A.
 | language = Russian
 | publisher = Inst. of Mathematics, Novosibirsk
 | series = Ph.D. thesis
 | title = On perfect arc and chord intersection graphs
 | year = 1984}}. As cited by {{harvtxt|Ageev|1996}}.
*{{citation
 | last = Keil | first = J. Mark
 | doi = 10.1016/0166-218X(93)90178-Q
 | issue = 1
 | journal = Discrete Applied Mathematics
 | pages = 51–63
 | title = The complexity of domination problems in circle graphs
 | volume = 42
 | year = 1993| doi-access = free
 }}.
*{{citation
 | doi = 10.1142/S0129054196000099
 | last = Kloks | first = Ton
 | title = Treewidth of Circle Graphs
 | journal = Int. J. Found. Comput. Sci.
 | year = 1996
 | volume = 7
 | pages = 111–120
 | issue = 2}}.
*{{citation
 | last1 = Kloks | first1 = T.
 | last2 = Kratsch | first2 = D.
 | last3 = Wong | first3 = C. K.
 | doi = 10.1006/jagm.1998.0936
 | issue = 2
 | journal = Journal of Algorithms
 | pages = 272–289
 | title = Minimum fill-in on circle and circular-arc graphs
 | volume = 28
 | year = 1998}}.
*{{citation
 | last = Kostochka | first = A.V.
 | language = Russian
 | mr = 0945704
 | journal = Trudy Instituta Mathematiki
 | pages = 204–226
 | title = Upper bounds on the chromatic number of graphs
 | volume = 10
 | year = 1988}}. As cited by {{harvtxt|Ageev|1996}}.
*{{citation
 | last1 = Kostochka | first1 = A.V.
 | last2 = Kratochvíl | first2 = J.
 | doi = 10.1016/S0012-365X(96)00344-5
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 299–305
 | title = Covering and coloring polygon-circle graphs
 | volume = 163
 | year = 1997| doi-access = free
 }}.
*{{citation
 | last1 = Nash | first1 = Nicholas
 | last2 = Gregg | first2 = David
 | doi = 10.1016/j.ipl.2010.05.016
 | issue = 16
 | journal = [[Information Processing Letters]]
 | pages = 630–634
 | title = An output sensitive algorithm for computing a maximum independent set of a circle graph
 | volume = 116
 | year = 2010| hdl = 10344/2228
 | hdl-access = free
 }}.
*{{citation
 | last = Spinrad | first = Jeremy
 | doi = 10.1006/jagm.1994.1012
 | issue = 2
 | journal = Journal of Algorithms
 | pages = 264–282
 | title = Recognition of circle graphs
 | volume = 16
 | year = 1994}}.
*{{citation
 | last = Tiskin | first = Alexander
 | pages = 1287–1296
 | contribution = Fast distance multiplication of unit-Monge matrices. 
 | title = Proceedings of ACM-SIAM SODA 2010
 | year = 2010}}.
*{{citation
 | last = Unger | first = Walter
 | contribution = On the ''k''-colouring of circle-graphs
 | doi = 10.1007/BFb0035832
 | location = Berlin
 | pages = 61–72
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = STACS 88: 5th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11–13, 1988, Proceedings
 | volume = 294
 | year = 1988}}.
*{{citation
 | last = Unger | first = Walter
 | contribution = The complexity of colouring circle graphs
 | doi = 10.1007/3-540-55210-3_199
 | location = Berlin
 | pages = 389–400
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings
 | volume = 577
 | year = 1992}}.
*{{citation
 | last1 = Wessel | first1 = W.
 | last2 = Pöschel | first2 = R.
 | contribution = On circle graphs
 | editor-last = Sachs | editor-first = Horst | editor-link = Horst Sachs
 | pages = 207–210
 | publisher = B.G. Teubner
 | series = Teubner-Texte zur Mathematik
 | title = Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984
 | volume = 73
 | year = 1985}}. As cited by {{harvtxt|Unger|1988}}.
{{refend}}

[[Category:Circles]]
[[Category:Intersection classes of graphs]]
[[Category:Geometric graphs]]