Planarization of Graphs Embedded on Surfaces
Planarization of Graphs Embedded on Surfaces
复制标题
嵌入表面的图形的平面化
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
S. M. Venkatesan
中科院分区：
文献类型：
--
作者：
H. Djidjev;S. M. Venkatesan
图的平面化集是一组边或顶点的集合，去除这些边或顶点会得到一个平面图。证明了：若G是最大度为d且亏格为g的n-顶点图，则存在一个O（n-dgn）边的平面化集.这个结果在一个常数因子内是紧的。对于平面化顶点集和嵌入在不可定向曲面上的图，也得到了类似的结果。如果给定G在亏格g的曲面上的一个嵌入，则可以在O（n+g）时间内找到平面化的边集和顶点集。我们还构造了一个近似算法，找到一个O（n log g）的平面化顶点集的G在O（n log g）的时间，如果没有genus-g嵌入作为输入。
A planarizing set of a graph is a set of edges or vertices whose removal leaves a planar graph. It is shown that, if G is an n-vertex graph of maximum degree d and orientable genus g, then there exists a planarizing set of O(√dgn) edges. This result is tight within a constant factor. Similar results are obtained for planarizing vertex sets and for graphs embedded on nonorientable surfaces. Planarizing edge and vertex sets can be found in O(n+g) time, if an embedding of G on a surface of genus g is given. We also construct an approximation algorithm that finds an O(√gn log g) planarizing vertex set of G in O(n log g) time if no genus-g embedding is given as an input.