Vertex insertion approximates the crossing number of apex graphs
Vertex insertion approximates the crossing number of apex graphs
复制标题
顶点插入近似顶点图的交叉数
DOI：
10.1016/j.ejc.2011.09.009
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Petra Mutzel
中科院分区：
文献类型：
--
作者：
Markus Chimani;Petr Hliněný;Petra Mutzel
顶点图是指只需移除一个顶点v即可使其成为平面图的图G。我们证明了通过解决顶点插入问题，即在平面图的最优选择的平面嵌入中插入一个顶点和关联边，这样的图的交叉数可以近似为Δ(G−v)⋅d(V)/2的因子。由于后一个问题可以在多项式时间内求解，从而为有界度顶点图的交叉数问题建立了第一个多项式固定因子逼近算法。进一步，我们推广了这一结果，证明了在平面图中插入多条边或多个顶点的最优解也近似于所得到的图的交叉数。
An apex graph is a graph G from which only one vertex v has to be removed to make it planar. We show that the crossing number of such G can be approximated up to a factor of Δ(G−v)⋅d(v)/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Since the latter problem can be solved in polynomial time, this establishes the first polynomial fixed-factor approximation algorithm for the crossing number problem of apex graphs with bounded degree. Furthermore, we extend this result by showing that the optimal solution for inserting multiple edges or vertices into a planar graph also approximates the crossing number of the resulting graph.
登录
查看更多内容
精确交叉最小化的新方法
DOI：
10.1007/978-3-540-87744-8_24
发表时间：
2008
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
Markus Chimani;Petra Mutzel;I. Bomze
通讯作者：
I. Bomze
DOI：
10.1016/j.endm.2007.07.037
发表时间：
2007
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
I. Gitler;Petr Hliněný;J. Leaños;G. Salazar
通讯作者：
G. Salazar
DOI：
10.1007/3-540-46648-7_18
发表时间：
1999
期刊：
Environment and Planning B: Urban Analytics and City Science
影响因子：
--
作者：
Petra Mutzel;T. Ziegler
通讯作者：
T. Ziegler
改进图形绘制中交叉点的近似值
DOI：
10.1145/335305.335340
发表时间：
2000
期刊：
Environment and Planning B: Urban Analytics and City Science
影响因子：
--
作者：
G. Even;S. Guha;B. Schieber
通讯作者：
B. Schieber
交叉数的更紧密的基于插入的近似
影响因子：
1
作者：
M. Chimani;P. Hlinĕný
通讯作者：
P. Hlinĕný