Pathwidth of outerplanar graphsReport as inadecuate




Pathwidth of outerplanar graphs - Download this document for free, or read online. Document in PDF available to download.

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , 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.





Author: David Coudert - Florian Huc - Jean-Sébastien Sereni -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents