Edge Separators for Planar Graphs and Their Applications
Edge Separators for Planar Graphs and Their Applications
复制标题
平面图的边分离器及其应用
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
I. Vrto
中科院分区：
文献类型：
--
作者：
K. Diks;H. Djidjev;O. Sýkora;I. Vrto
我们证明了每一个顶点数为n且最大度为k的平面图都有一个0（n = kn）-边分离子。这改进了已知的关于顶点度以常数为界的图的边分离符的结果。证明了任意n个顶点的最大度为k的树都可以通过去掉0（klogn/logk）条边而分成≤ n / 2个顶点的两部分.两个分隔符的大小都是存在最优的。我们将边缘分离器应用于平均成本有效的嵌入到二叉树，网格和超立方体的度k的平面图。
We show that every planar graph with n vertices and a maximal degree k has an 0(√kn)-edge separator. This improves known results about edge separators of graphs with vertex degree bounded by a constant. We show that any n vertex tree of a maximal degree k can be divided into two parts of ≤ n / 2 vertices by removing 0(klog n/log k) edges. The sizes of both separators are existentially optimal. We apply the edge separator to average cost efficient embeddings of planar graphs of degree k into binary trees, meshes and hypercubes.