Pathwidth of outerplanar graphs

David Coudert 1 Florian Huc 1 Jean-Sébastien Sereni 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00429216
Contributor : David Coudert <>
Submitted on : Sunday, November 1, 2009 - 9:30:25 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM
Long-term archiving on : Thursday, June 17, 2010 - 6:59:07 PM

File

CHS-JGT06.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

336

Files downloads

245