✦ LIBER ✦

Planar Graphs on Nonplanar Surfaces

✍ Scribed by Bojan Mohar; Neil Robertson

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 738 KB
Volume: 68
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.0058

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that embeddings of planar graphs in arbitrary surfaces other than the 2-sphere have a special structure. It turns out that these embeddings can be described in terms of noncontractible curves in the surface, meeting the graph in at most two points (which may taken to be vertices of the graph). The close connection between the homology group of the surface and the planar graph embeddings is perhaps the most interesting aspect of this study. Some important consequences follow from these results. For example, any two embeddings of a planar graph in the same surface can be obtained from each other by means of simple local reembeddings very similar to Whitney's switchings.

📜 SIMILAR VOLUMES

Circular embeddings of planar graphs in

Circular embeddings of planar graphs in nonspherical surfaces

✍ R.B. Richter; P.D. Seymour; J. Širáň 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 506 KB

We show that every 3-connected planar graph has a circular embedding in some nonspherical surface. More generally, we characterize those planar graphs that have a 2-representative embedding in some nonspherical surface. This is proved in Section 3. Standard results in the theory show that it suffic

On planar hypohamiltonian graphs

✍ Gábor Wiener; Makoto Araya 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for eve

On generating planar graphs

✍ David Barnette 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 699 KB

A 3-valent graph G 1s cyclically n-connected provided one must cut at least n edges in ori4r to separate any two circuits of 6. If G is cyclically n-connected but any separation of G by cutting n edges yields a component consisting of a simple circuit, then we say that G is ' strong& cyclicaZZy n-co

On paths in planar graphs

✍ Sanders, Daniel P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 2 views

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy.

Antisymmetric flows on planar graphs

✍ T. H. Marshall 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB

## Abstract We prove that every oriented planar graph admits a homomorphism to the Paley tournament __P__~271~ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210

A note on planar graphs

✍ David P. Brown; Alan Budner 📂 Article 📅 1965 🏛 Elsevier Science 🌐 English ⚖ 612 KB

Some new properties of the distribution of elements and vertices with respect to the windows of a connected planar graph G are established. It is also shown that a window matrix of G has properties similar to the properties of an incidence matrix of a graph which is not necessarily planar. A method