Structural results on circular-arc graphs and circle graphs: A survey and the main open problems
Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous interesting results have been reported. Many subclasses of both circular-arc...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | INPR |
| Lenguaje: | English |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v_n_p_Duran |
| Aporte de: |
| Sumario: | Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous interesting results have been reported. Many subclasses of both circular-arc graphs and circle graphs have been defined and different characterizations formulated. In this survey, we summarize the most important structural results related to circular-arc graphs and circle graphs and present the main open problems. © 2013. |
|---|