Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic

zbMATH Open1430.05020arXiv1806.11333MaRDI QIDQ5207850FDOQ5207850

Authors: Kengo Enami 

Publication date: 13 January 2020

Abstract: Whitney's theorem states that every 3-connected planar graph is uniquely embeddable on the sphere. On the other hand, it has many inequivalent embeddings on another surface. We shall characterize structures of a $3$-connected $3$-regular planar graph $G$ embedded on the projective-plane, the torus and the Klein bottle, and give a one-to-one correspondence between inequivalent embeddings of $G$ on each surface and some subgraphs of the dual of $G$ embedded on the sphere. These results enable us to give explicit bounds for the number of inequivalent embeddings of $G$ on each surface, and propose effective algorithms for enumerating and counting these embeddings.

Full work available at URL: https://arxiv.org/abs/1806.11333

Recommendations

• Flexibility of polyhedral embeddings of graphs in surfaces
• Enumeration of projective-planar embeddings of graphs
• scientific article; zbMATH DE number 2163939
• A simple and elementary proof of Whitney's unique embedding theorem
• Planar graphs on nonplanar surfaces

zbMATH Keywords

cubic graphplanar graphflexibilitygenus distributioninequivalent embeddings

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Connectivity (05C40)

Cited In (10)

• Circular embedding of planar graphs in nonspherical surfaces
• Embedding K3,3 and K5 on the Double Torus
• 3-edge-connected embeddings have few singular edges
• 2‐complexes with unique embeddings in 3‐space
• Euler-genus distributions of cubic caterpillar-Halin graphs
• Title not available (Why is that?)
• A simple and elementary proof of Whitney's unique embedding theorem
• Title not available (Why is that?)
• Flexibility of polyhedral embeddings of graphs in surfaces
• Title not available (Why is that?)

This page was built for publication: Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207850)