## Enami, Kengo - Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic

dmtcs:4656 - Discrete Mathematics & Theoretical Computer Science, September 27, 2019, vol. 21 no. 4
Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic

Authors: Enami, Kengo

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.

DOI : 10.23638/DMTCS-21-4-14
Volume: vol. 21 no. 4
Section: Graph Theory
Published on: September 27, 2019
Submitted on: July 3, 2018
Keywords: Mathematics - Combinatorics