Structural results on circular-arc graphs and circle graphs: A survey and the main open problems

作者：Duran Guillermo^*; Grippo Luciano N; Safe Martin D

来源：Discrete Applied Mathematics, 2014, 164: 427-443.

DOI：10.1016/j.dam.2012.12.021

• Circle graphs
• Circular-arc graphs
• Forbidden subgraph characterizations
• Interval graphs
• Matrix characterizations
• Permutation graphs

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.

• 出版日期2014-2-19