Circle graph
From Wikipedia, the free encyclopedia
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.
Spinrad (1994) gives an 
recognition algorithm for circle graphs that also computes a circle model of the input graph if it is a circle graph.
Contents |
[edit] 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
time.[1]
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.[2]
- Circle graphs must be measured properly for the right outcome of the graph.
[edit] Relation to other graph classes
[edit] Equivalent classes
A graph is a circle graph if and only if it is an interval overlap graph.[3]
[edit] Superclasses
- String graphs, a broader class of intersection graphs, includes circle graphs as a special case
[edit] Subclasses
[edit] Notes
[edit] References
- Spinrad, Jeremy (1994), “Recognition of circle graphs”, Journal of Algorithms 16 (2): 264–282, DOI 10.1006/jagm.1994.1012
- Kloks, T.; Kratsch, D. & Wong, C. K. (1998), “Minimum fill-in on circle and circular-arc graphs”, Journal of Algorithms 28 (2): 272–289, DOI 10.1006/jagm.1998.0936
- Keil, J. Mark (1993), “The complexity of domination problems in circle graphs”, Discrete Applied Mathematics 42 (1): 51–63, DOI 10.1016/0166-218X(93)90178-Q
- Gavril, Fanica (1973), “Algorithms for a maximum clique and a maximum independent set of a circle graph”, Networks 3 (3): 261–273, DOI 10.1002/net.3230030305
