Quick links

Recognizing Circle Graphs in Polynomial Time

Report ID:
TR-059-86
Date:
June 1986
Pages:
74
Download Formats:
[PDF]

Abstract:

Our main result is an O(|V|x|E|) time 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. Furthermore, as a substep of our algorithm, we show how to find in O(|V|x|E|) time a decomposition of a graph into prime graphs, thereby improving on a result of Cunningham.

Follow us: Facebook Twitter Linkedin