Characterizations and recognition of circular-arc graphs and subclasses: A survey |
| |
Authors: | Min Chih Lin Jayme L Szwarcfiter |
| |
Institution: | a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina b Instituto de Matemática, NCE and COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil |
| |
Abstract: | Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms. |
| |
Keywords: | Algorithms Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs |
本文献已被 ScienceDirect 等数据库收录! |
|