×

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
Full Text: DOI