On the genera of polyhedral embeddings of cubic graph
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3
Cet article a éte moissonné depuis la source Episciences
In this article we present theoretical and computational results on the existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs. We also describe an efficient algorithm to compute all polyhedral embeddings of a given cubic graph and constructions for cubic graphs with some special properties of their polyhedral embeddings. Some key results are that even cubic graphs with a polyhedral embedding on the torus can also have polyhedral embeddings in arbitrarily high genus, in fact in a genus {\em close} to the theoretical maximum for that number of vertices, and that there is no bound on the number of genera in which a cubic graph can have a polyhedral embedding. While these results suggest a large variety of polyhedral embeddings, computations for up to 28 vertices suggest that by far most of the cubic graphs do not have a polyhedral embedding in any genus and that the ratio of these graphs is increasing with the number of vertices.
@article{DMTCS_2021_23_3_a6,
author = {Brinkmann, Gunnar and Tucker, Thomas and Van Cleemput, Nico},
title = {On the genera of polyhedral embeddings of cubic graph},
journal = {Discrete mathematics & theoretical computer science},
year = {2021-2022},
volume = {23},
number = {3},
doi = {10.46298/dmtcs.6729},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6729/}
}
TY - JOUR AU - Brinkmann, Gunnar AU - Tucker, Thomas AU - Van Cleemput, Nico TI - On the genera of polyhedral embeddings of cubic graph JO - Discrete mathematics & theoretical computer science PY - 2021-2022 VL - 23 IS - 3 UR - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6729/ DO - 10.46298/dmtcs.6729 LA - en ID - DMTCS_2021_23_3_a6 ER -
%0 Journal Article %A Brinkmann, Gunnar %A Tucker, Thomas %A Van Cleemput, Nico %T On the genera of polyhedral embeddings of cubic graph %J Discrete mathematics & theoretical computer science %D 2021-2022 %V 23 %N 3 %U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6729/ %R 10.46298/dmtcs.6729 %G en %F DMTCS_2021_23_3_a6
Brinkmann, Gunnar; Tucker, Thomas; Van Cleemput, Nico. On the genera of polyhedral embeddings of cubic graph. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3. doi: 10.46298/dmtcs.6729
Cité par Sources :