论文标题
在立方图的多面体嵌入属上
On the genera of polyhedral embeddings of cubic graph
论文作者
论文摘要
在本文中，我们介绍了有关图的多面体嵌入的理论和计算结果。重点是立方图。我们还描述了一种有效的算法，以计算给定立方图的所有多面体嵌入以及具有其多面体嵌入的某些特殊特性的立方图的构造。一些关键结果是，即使是在圆环上嵌入多面体嵌入的立方图也可以在任意属的属中具有多面体嵌入，实际上，在该数量的顶点的理论最大值中，实际上是在属的属中，并且在立方图中没有包含的属数量的属数，并且在这些属上没有构造的属性。尽管这些结果表明各种各样的多面体嵌入，但多达28个顶点的计算表明，到目前为止，大多数立方图在任何属中都没有多面体嵌入，并且这些图的比率随着顶点的数量而增加。
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.
