Circle graph

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.

For instance, Kloks (1996) showed that the treewidth of a circle graph can be determined, and an optimal tree decomposition constructed, in O(n3) time.

However, there are also problems that remain NP-complete when restricted to circle graphs.

[10] The problem of coloring triangle-free squaregraphs is equivalent to the problem of representing squaregraphs as isometric subgraphs of Cartesian products of trees; in this correspondence, the number of colors in the coloring corresponds to the number of trees in the product representation.

[11] Circle graphs arise in VLSI physical design as an abstract representation for a special case for wire routing, known as "two-terminal switchbox routing".

[12] 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.