Skip to Main content Skip to Navigation
Reports

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, 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 $1$ for every biconnected planar graph. Fomin proved that the second conjecture is true for all planar triangulations, and made a stronger conjecture about the linear width of planar graphs. First, we construct for each p>=1 a biconnected outerplanar graph of pathwidth 2p+1 whose (geometric) dual has pathwidth p+1, thereby disproving all three conjectures. Then 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 1. A tight interval for the studied relation is therefore obtained, and we show that all the gaps within the interval actually happen.
Document type :
Reports
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070220
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 7:31:32 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:38:38 PM

Identifiers

  • HAL Id : inria-00070220, version 1

Collections

Citation

David Coudert, Florian Huc, Jean-Sébastien Sereni. Pathwidth of outerplanar graphs. [Research Report] RR-5804, INRIA. 2006, pp.12. ⟨inria-00070220⟩

Share

Metrics

Record views

411

Files downloads

1357