Kengo Enami - 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 - https://doi.org/10.23638/DMTCS-21-4-14
Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristicArticle

Authors: Kengo Enami

    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.


    Volume: vol. 21 no. 4
    Section: Graph Theory
    Published on: September 27, 2019
    Accepted on: September 6, 2019
    Submitted on: July 3, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1191 times.
    This article's PDF has been downloaded 1154 times.