The Planar Separator Theorem
The Planar Separator Theorem
复制标题
平面分隔定理
DOI：
10.1007/978-1-4612-4400-4_15
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
D. Kozen
中科院分区：
文献类型：
--
作者：
D. Kozen
Lipton和Tarjan [73]的平面分离子定理指出，在任意无向平面图G中，存在一个小的分离子S; V，去掉它，只剩下两个不相交的顶点集A，B S; V，它们之间没有边;而且，A和B中的每一个至多是S; V的大小的一个常数分数。
The Planar Separator Theorem of Lipton and Tarjan [73J says that in any undirected planar graph G there exists a small sepamtor 8 S; V whose removal leaves two disjoint sets of vertices A, B S; V with no edge between them; moreover, each of A and B is at most a constant fraction of the size of