𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of outerplanar graphs

✍ Scribed by L. Oubiña; R. Zucchello

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
898 KB
Volume
51
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

l[Rt G be a planar graph and W a set of vertices, G is W-outerplanar if it can be embedded in the plane so that all vertices of W lie on the exterior face. We give a characterization of these graphs by forbidden subgraphs, an upper bound on the number of edges, and other properties which lead to an algorithm of W-outerplanarity testing.

📜 SIMILAR VOLUMES

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

Pathwidth of outerplanar graphs
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

Characterizations of outerplanar graphs
Characterizations of outerplanar graphs
✍ Maciej M. Sysło 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 750 KB

The paper presents several characterizations of outerp:anar graphs, some of them are counterparts of the well-known characterizations of planar graphs and the other provide very efficient tools for outerplanarity testing, coding (i.e. isomorphism testing), and counting such graphs. Finally, we attem

Centers of maximal outerplanar graphs
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
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