Treewidth of cocomparability graphs and a new order-theoretic parameter

We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively.This work was done while the second author stayed at the LIRMM within the PROCOPE program of the DAAD. Both authors acknowledge the support by the PROCOPE program. The second author also acknowledges partial support by the Deutsche Forschungsgemeinschaft under Grant No Mo446/3-1.