Editing Circle graph (section)

==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>