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.
recognition algorithm for circle graphs that also computes a circle model of the input graph if it is a circle graph.
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 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
A graph is a circle graph if and only if it is an interval overlap graph