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

MaRDI QIDQ5207850zbMATH OpenFDO

Authors Kengo Enami

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1806.11333, https://dmtcs.episciences.org/5784/pdf

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)

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.

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

Cited in

(10)

• scientific article; zbMATH DE number 1161284 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 2163939 (Why is no real title available?)
• A simple and elementary proof of Whitney's unique embedding theorem
• Flexibility of polyhedral embeddings of graphs in surfaces
• scientific article; zbMATH DE number 7535271 (Why is no real title available?)

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)