Geodesic
Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_2019_21_4_a10,
     author = {Enami, Kengo},
     title = {Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative {Euler} characteristic},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2019},
     volume = {21},
     number = {4},
     doi = {10.23638/DMTCS-21-4-14},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-14/}
}
TY  - JOUR
AU  - Enami, Kengo
TI  - Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-14/
DO  - 10.23638/DMTCS-21-4-14
LA  - en
ID  - DMTCS_2019_21_4_a10
ER  - 
%0 Journal Article
%A Enami, Kengo
%T Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-14/
%R 10.23638/DMTCS-21-4-14
%G en
%F DMTCS_2019_21_4_a10
Enami, Kengo. Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi: 10.23638/DMTCS-21-4-14

Cité par Sources :