Rectangular duals of planar graphs
Rectangular duals of planar graphs
复制标题
平面图的矩形对偶
DOI：
10.1002/net.3230150202
复制
发表时间：
1985
期刊：
影响因子：
2.1
通讯作者：
E. Kinnen
中科院分区：
文献类型：
--
作者：
K. Kozminski;E. Kinnen
让一个立方体的一个面被分成矩形，其中没有4个相交于一个点。这种配置的对偶图是一个4连通的三角平面图。本文证明了任何至少有6个顶点且至少有一个顶点为4次的4连通平面三角剖分与一面剖分为矩形的立方体是对偶的。这个结果的证明包含一个隐式算法获得这样的解剖。本文还讨论了一个相关的问题：给定一个图G，除外表面外所有的面都是三角形，是否存在一个矩形的剖分，使得G描述了矩形之间的邻接关系？
Let one face of a cube be dissected into rectangles, no 4 of which meet at a single point. The dual graph of this configuration is a 4-connected triangulated plane graph. This paper shows that any 4-connected plane triangulation with at least 6 vertices and at least one vertex of degree 4 is dual to a cube with one face dissected into rectangles. The proof of this result contains an implicit algorithm for obtaining such a dissection. The paper also discusses a related problem: Given a graph G with all faces triangular except the outer face, does there exist a dissection of a rectangle into rectangles for which G describes the adjacency relations among the rectangles?