Towards Characterizing Graphs with a Sliceable Rectangular Dual
Towards Characterizing Graphs with a Sliceable Rectangular Dual
复制标题
使用可切片矩形对偶来表征图
DOI：
10.1007/978-3-319-27261-0_38
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
B. Speckmann
中科院分区：
文献类型：
--
作者：
Vincent Kusters;B. Speckmann
设$$\数学{G}$$是平面三角化图。$$\数学{G}$$的矩形对偶是将矩形R划分为内部不相交的矩形的集合$$\数学{R}$$，每个顶点一个，使得两个区域相邻当且仅当相应的顶点由一条边连接。如果矩形对偶可以沿水平线或垂直线递归细分，则它是可分割的。一个图是矩形的，如果它有一个矩形对偶，那么它是矩形的；如果它有一个可分的矩形对偶，它是可分的。矩形图有一个明确的刻画。然而，对可割图的充分刻画仍然是缺乏的。目前最好的结果是Yeap和Sarrafzadeh，1995证明了所有没有分离4圈的矩形图都是可割的。本文引入了一类递归定义的图，并证明了这类图正是恰好有一个分离4-圈的不可割图。
Let $$\mathcal {G} $$ be a plane triangulated graph. A rectangular dual of $$\mathcal {G} $$ is a partition of a rectangle R into a set $$\mathcal {R} $$ of interior-disjoint rectangles, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge. A rectangular dual is sliceable if it can be recursively subdivided along horizontal or vertical lines. A graph is rectangular if it has a rectangular dual and sliceable if it has a sliceable rectangular dual. There is a clear characterization of rectangular graphs. However, a full characterization of sliceable graphs is still lacking. The currently best result Yeap and Sarrafzadeh, 1995 proves that all rectangular graphs without a separating 4-cycle are sliceable. In this paper we introduce a recursively defined class of graphs and prove that these graphs are precisely the nonsliceable graphs with exactly one separating 4-cycle.