Treewidth of circle graphs. (English) Zbl 0852.68069
Summary: We show that the treewidth of a circle graph can be computed in polynomial time. A circle graph is a graph that is isomorphic to the intersection graph of a finite collection of chords of a circle. The TREEWIDTH problem can be viewed upon as the problem of finding a chordal embedding of the graph that minimizes the clique number. Our algorithm to determine the treewidth of a circle graph can be implemented to run in \(O (n^3)\) time, where \(n\) is the number of vertices of the graph.
MSC:
68R10 | Graph theory (including graph drawing) in computer science |
68Q25 | Analysis of algorithms and problem complexity |