✦ LIBER ✦

Enumeration of projective-planar embeddings of graphs

✍ Scribed by Seiya Negami

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 562 KB
Volume: 62
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90217-7

No coin nor oath required. For personal study only.

✦ Synopsis

It will be shown that the number of equivalence classes of embeddings of a 3-connected nonplanar graph into a projective plane coincides with the number of isomorphism classes of planar double coverings of the graph and a combinatorial method to determine the number will be developed.

📜 SIMILAR VOLUMES

Unique and faithful embeddings of projec

Unique and faithful embeddings of projective-planar graphs

✍ Seiya Negami 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

A graph G is uniquelyembeddable in a surface f 2 if for any two embeddings f,,f2 : G + f 2 , there exists an isomorphism u : G + G and a homeo- admits an embedding f : G + F2 such that for any isomorphism (T : G + G, there is a homeomorphism h : F 2 f 2 with h . f = f . u. It will be shown that if

Bounding the number of embeddings of 5-c

Bounding the number of embeddings of 5-connected projective-planar graphs

✍ Shigeru Kitakubo 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

A graph is said to be projective-planar if it is nonplanar and is embeddable in a projective plane. In this paper we show that the numbers of projectiveplanar embeddings (up to equivalence) of all 5-connected graphs have an upper bound c( 1120).

Re-embedding structures of 4-connected p

Re-embedding structures of 4-connected projective-planar graphs

✍ Yusuke Suzuki 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

We identify the structures of 4-connected projective-planar graphs which generate their inequivalent embeddings on the projective plane, showing two series of graphs the number of whose inequivalent embeddings is held by O(n) with respect to the number of its vertices n.

An algebraic characterization of project

An algebraic characterization of projective-planar graphs

✍ Lowell Abrams; Daniel C. Slilaty 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract We give a detailed algebraic characterization of when a graph __G__ can be imbedded in the projective plane. The characterization is in terms of the existence of a dual graph __G__\* on the same edge set as __G__, which satisfies algebraic conditions inspired by homology groups and inte

On convex embeddings of planar 3-connect

On convex embeddings of planar 3-connected graphs

✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

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 thi

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