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.

Source : oai:arXiv.org:1806.11333

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