✦ LIBER ✦

Augmenting Outerplanar Graphs

✍ Scribed by Goos Kant

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 269 KB
Volume: 21
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0034

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we show that for outerplanar graphs G the problem of augmenting G by adding a minimum number of edges such that the augmented graph GЈ is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space. It is also shown that augmenting a biconnected outerplanar graph to a maximal outerplanar graph while minimizing the maximum degree can be achieved in polynomial time. These augmentation problems arise in the area of drawing outerplanar graphs.

📜 SIMILAR VOLUMES

Pathwidth of outerplanar graphs

✍ David Coudert; Florian Huc; Jean-Sébastien Sereni 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

## 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 (geo

On list-coloring outerplanar graphs

✍ Joan P. Hutchinson 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

## Abstract We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors __L__ (__v__ ) for each vertex __v__ such that $|L(v)|\geq\min\{{\deg}(v),4\}$ (resp., $|L(v)|\geq{\min}\{{\deg}(v),5\}$) can be __L__‐list‐colored (except when

Centers of maximal outerplanar graphs

✍ Andrzej Proskurowski 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB

## Abstract The center of a graph is defined to be the subgraph induced by the set of vertices that have minimum eccentricities (i.e., minimum distance to the most distant vertices). It is shown that only seven graphs can be centers of maximal outerplanar graphs.

Outerplanar Partitions of Planar Graphs

✍ Kiran S. Kedlaya 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 254 KB

An outerplanar graph is one that can be embedded in the plane so that all of the vertices lie on one of the faces. We investigate a conjecture of Chartrand, Geller, and Hedetniemi, that every planar graph can be edge-partitioned into two outerplanar subgraphs. We refute the stronger statement that e

A characterization of ?-outerplanar grap

A characterization of ?-outerplanar graphs

✍ Wargo, Lawrence 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 528 KB

Chartrand and Harary have shown that if G is a non-outerplanar graph such that, for every edge e, both the deletion G \ e and the contraction G/e of e from G are outerplanar, then G is isomorphic to K4 or K2,3. An a-outerplanar graph is a graph which is not outerplanar such that, for some edge a , b

Game chromatic number of outerplanar gra

Game chromatic number of outerplanar graphs

✍ Guan, D. J.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs.