Recognizing Circle Graphs in Polynomial Time
Report ID: TR-059-86Author: Gabor, Csaba P. / Hsu, Wen-Lian / Supowit, Kenneth J.
Date: 1986-07-00
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.