𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Essential and Inessential Polygons in Embedded Graphs

✍ Scribed by R.Bruce Richter; R.P. Vitray

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
163 KB
Volume
84
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, we present a number of results of the following type: A given subgraph of an embedded graph either is embedded in a disc or it has a face chain containing a non-contractible closed path. Our main application is to prove that any two faces of a 4-representative embedding are simultaneously contained in a disc bounded by a polygon. This result is used to prove the existence of N(r -1)/8M pairwise disjoint, pairwise homotopic non-contractible separating polygons in an r-representative orientable embedding. Our proof of this latter result is simple and mechanical.

πŸ“œ 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

Nearly light cycles in embedded graphs a
Nearly light cycles in embedded graphs and crossing-critical graphs
✍ Mario LomelΓ­; Gelasio Salazar πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 101 KB

## Abstract We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large __k__‐crossing‐critical graph has crossing number a

3-Coloring graphs embedded in surfaces
3-Coloring graphs embedded in surfaces
✍ Zhao, Yue πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 66 KB πŸ‘ 3 views

In this article, we show that there exists an integer k(Ξ£)

On self duality of pathwidth in polyhedr
On self duality of pathwidth in polyhedral graph embeddings
✍ Fedor V. Fomin; Dimitrios M. Thilikos πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 211 KB

## 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 embedd

On the number of triangular embeddings o
On the number of triangular embeddings of complete graphs and complete tripartite graphs
✍ M. J. Grannell; M. Knor πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 159 KB

## Abstract We prove that for every prime number __p__ and odd __m__>1, as __s__β†’βˆž, there are at least __w__ face 2‐colorable triangular embeddings of __K__~__w, w, w__~, where __w__ = __m__Β·__p__^__s__^. For both orientable and nonorientable embeddings, this result implies that for infinitely many