Treewidth of Circular-Arc Graphs
Ravi Sundaram, Karan Sher Singh, Chandrasekharan Pandu Rangan · SIAM Journal on Discrete Mathematics · 1994
The treewidth of a graph is one of the most important graph-theoretic parameters from the algorithmic point of view. However, computing the treewidth and constructing a corresponding tree-decomposition for a general graph is NP-complete. This paper presents an algorithm for computing the treewidth and constructing a corresponding tree-decomposition for circular-arc graphs in $O( n^3 )$ time.