Pathwidth of outerplanar graphs

David Coudert (1) , Florian Huc (1) , Jean-Sébastien Sereni (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen.

Domaines: Mathématique discrète [cs.DM]

David Coudert, Florian Huc, Jean-Sébastien Sereni. Pathwidth of outerplanar graphs. Journal of Graph Theory, 2007, 55 (1), pp.27 - 41. ⟨10.1002/jgt.20218⟩. ⟨inria-00429216⟩