Planar Crossing Numbers of Graphs of Bounded Genus
Planar Crossing Numbers of Graphs of Bounded Genus
复制标题
有界亏格图的平面交叉数
DOI：
--
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
I. Vrto
中科院分区：
文献类型：
--
作者：
H. Djidjev;I. Vrto
Pach和Tóth证明了任何亏格为g且最大度为d的n-顶点图的平面交叉数至多为cgdn，其中c>1。我们改进了这一结果，通过减少到O（dgn）的界限，也证明了我们的结果是紧在一个常数因子。我们的证明是建设性的，并产生一个算法的时间复杂度为O（dgn）。作为我们的主要结果的一个结果，我们显示了平面交叉数和表面交叉数之间的关系。
Pach and Tóth proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most cgdn, for a constant c>1. We improve on this result by decreasing the bound to O(dgn), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity O(dgn). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.