𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On self duality of pathwidth in polyhedral graph embeddings

✍ Scribed by Fedor V. Fomin; Dimitrios M. Thilikos

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
211 KB
Volume
55
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a 3‐connected planar graph and G^*^ be its dual. We show that the pathwidth of G^*^ is at most 6 times the pathwidth of G. We prove this result by relating the pathwidth of a graph with the cut‐width of its medial graph and we extend it to bounded genus embeddings. We also show that there exist 3‐connected planar graphs such that the pathwidth of such a graph is at least 1.5 times the pathwidth of its dual. Β© 2007 Wiley Periodicals, Inc. J Graph Theory 55: 42–54, 2007

πŸ“œ SIMILAR VOLUMES

On the Connectivity of Graphs Embedded i
On the Connectivity of Graphs Embedded in Surfaces
✍ Michael D Plummer; Xiaoya Zha πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 376 KB

In a 1973 paper, Cooke obtained an upper bound on the possible connectivity of a graph embedded in a surface (orientable or nonorientable) of fixed genus. Furthermore, he claimed that for each orientable genus #>0 (respectively, nonorientable genus #Γ„ >0, #Γ„ {2) there is a complete graph of orientab

On the Number of Acute Triangles in a St
On the Number of Acute Triangles in a Straight-Line Embedding of a Maximal Planar Graph
✍ Atsushi Kaneko; Hiroshi Maehara; Mamoru Watanabe πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 80 KB

In this paper we show that any maximal planar graph with m triangles except the unbounded face can be transformed into a straight-line embedding in which at least WmΓ‚3X triangles are acute triangles. Moreover, we show that any maximal outerplanar graph can be transformed into a straight-line embeddi