
doi: 10.1002/jgt.20218
AbstractWe 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. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 27–41, 2007
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, triangulation, biconnected graphs
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, triangulation, biconnected graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
