Added to Favorites

Related Searches

Definitions

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 $\{mathcal\; O(n^2)\}$ 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:## Relation to other graph classes

### Equivalent classes

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

### Subclasses

## Notes

## References

## External links

- A minimum fill-in can be found in $\{mathcal\; O(n^3)\}$ 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.

- String graphs, a broader class of intersection graphs, includes circle graphs as a special case

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Friday October 10, 2008 at 09:17:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Friday October 10, 2008 at 09:17:19 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.