Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic
Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic
复制标题
DOI：
10.23638/dmtcs-21-4-14
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Kengo Enami
中科院分区：
文献类型：
--
作者：
Kengo Enami
惠特尼定理指出，每个三连通平面图在球面上都是唯一可嵌入的。另一方面，它在另一个表面上有许多不等价的嵌入。我们将表征嵌入在射影平面、环面和克莱因瓶上的 $3$ 连接的 $3$ 正则平面图 $G$ 的结构，并给出每个表面上的 $G$ 的不等价嵌入与嵌入在球体上的 $G$ 对偶的一些子图之间的一一对应关系。这些结果使我们能够为每个表面上 $G$ 的不等价嵌入的数量给出明确的界限，并提出有效的算法来枚举和计算这些嵌入。
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.