Definitions

# Circle graph

In graph theory, a circle graph is a graph whose vertices can be associated with chords of a circle such that two vertices are adjacent if and only if the corresponding chords in the circle intersect. gives an $\left\{mathcal O\left(n^2\right)\right\}$ recognition algorithm for circle graphs that also computes a circle model of the input graph if it is a circle graph.

## Algorithmic complexity

A number of problems that are NP-complete on general graphs have polynomial time algorithms when restricted to circle graphs. These include the following:

• A minimum fill-in can be found in $\left\{mathcal O\left(n^3\right)\right\}$ time.

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

• Minimum dominating set, minimum connected dominating set, and minimum total dominating set are all NP-complete.

## Relation to other graph classes

### Equivalent classes

A graph is a circle graph if and only if it is an interval overlap graph.