Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.04.003 | Discrete Mathematics |
Keywords | Field | DocType |
helly circular-arc graphs,algorithms,unit circular-arc graphs,proper circular-arc graphs,co-bipartite circular-arc graphs,circular-arc graphs | Discrete mathematics,Combinatorics,Modular decomposition,Indifference graph,Lévy family of graphs,Chordal graph,Clique-sum,Pathwidth,Trapezoid graph,Mathematics,Maximal independent set | Journal |
Volume | Issue | ISSN |
309 | 18 | Discrete Mathematics |
Citations | PageRank | References |
16 | 0.73 | 45 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Jayme L. Szwarcfiter | 2 | 546 | 45.97 |