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 {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:

  • 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.

Relation to other graph classes

Equivalent classes

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





External links

Search another word or see circle-graphon Dictionary | Thesaurus |Spanish
Copyright © 2014, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature