๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On convex embeddings of planar 3-connected graphs

โœ Scribed by Kelmans, Alexander

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
167 KB
Volume
33
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in this embedding. We give a simple proof of this last result. Our proof is based on the fact that a 3-connected graph admits an ear assembly having some special properties with respect to the nonseparating cycles of the graph. This fact may be interesting and useful in itself.

๐Ÿ“œ SIMILAR VOLUMES

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
โœ Enomoto, Hikoe; Ota, Katsuhiro ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 213 KB ๐Ÿ‘ 1 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) โ‰ค 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Cyclability of 3-connected graphs
Cyclability of 3-connected graphs
โœ Amel Harkat-Benhamdine; Hao Li; Feng Tian ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 151 KB
On embeddings of graphs containing noK5-
On embeddings of graphs containing noK5-minor
โœ Zhang, Cun-Quan ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 246 KB ๐Ÿ‘ 1 views

In this paper, w e proved that every 2-connected graph containing no &-minor has a closed 2-cell embedding on some 2-manifold surface.

On 3-colorable non-4-choosable planar gr
On 3-colorable non-4-choosable planar graphs
โœ Voigt, M.; Wirth, B. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 72 KB ๐Ÿ‘ 1 views

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v gets a color from a list L(v) of allowed colors. G is called k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifying conjectures of Erd

On the linear arboricity of planar graph
On the linear arboricity of planar graphs
โœ Wu, Jian-Liang ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 188 KB ๐Ÿ‘ 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree โˆ†. The conjecture has been proved to be true for graphs having โˆ† =