Treewidth and Pathwidth of Cocomparability Graphs of Bounded Dimension

摘要

In this paper we describe a polynomial time algorithm computing the treewidth ofa cocomparability graph of bounded dimension. We do not assume that an intersection model of the graph is part of the input.