episciences.org_6729_1660010557
1660010557
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
11
05
2021
vol. 23, no. 3
Graph Theory
On the genera of polyhedral embeddings of cubic graph
Gunnar
Brinkmann
Thomas
Tucker
Nico
Van Cleemput
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.
11
05
2021
6729
arXiv:2008.09467
10.48550/arXiv.2008.09467
https://arxiv.org/abs/2008.09467v2
https://arxiv.org/abs/2008.09467v1
10.46298/dmtcs.6729
https://dmtcs.episciences.org/6729

https://dmtcs.episciences.org/8657/pdf