Recognizing circle graphs in polynomial time
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 106-116
- https://doi.org/10.1109/sfcs.1985.47
Abstract
Our main result is a polynomialtime algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. Our algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices.Keywords
This publication has 9 references indexed in Scilit:
- On Comparability and Permutation GraphsSIAM Journal on Computing, 1985
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle GraphsSIAM Journal on Computing, 1985
- Decomposition of Directed GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- Finding maximum cliques in circle graphsNetworks, 1981
- The Complexity of Coloring Circular Arcs and ChordsSIAM Journal on Algebraic Discrete Methods, 1980
- An Efficient Test for Circular-Arc GraphsSIAM Journal on Computing, 1980
- Algorithms for a maximum clique and a maximum independent set of a circle graphNetworks, 1973
- Transitive Orientation of Graphs and Identification of Permutation GraphsCanadian Journal of Mathematics, 1971
- QUEUES, STACKS AND GRAPHSPublished by Elsevier ,1971