Crossing Number for Graphs with Bounded Pathwidth
Crossing Number for Graphs with Bounded Pathwidth
复制标题
具有有界路径宽度的图的交叉数
DOI：
10.1007/s00453-019-00653-x
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
P. Mutzel
中科院分区：
文献类型：
--
作者：
T. Biedl;M. Chimani;M. Derka;P. Mutzel
交叉数是在平面上绘制图形时成对边交叉的最小数量。只有极少数图类的确切交叉数是已知的或者至少存在恒定的近似比率。此外，到目前为止，还没有使用图分解的有界宽度（例如树宽或路径宽度）成功解决一般交叉数计算。在本文中，我们证明对于有界路径宽度 3 的最大图，交叉数是可处理的（即使在线性时间内）。该技术还表明，对于该图类，交叉数和直线（又称直线）交叉数是相同的，并且我们只需要一个网格即可实现这样的绘图。我们的技术可以进一步扩展，为路径宽度为 3 的一般图设计 2 近似。这里的一个关键要素是，具有分离对的图的交叉数可以使用其切割分量的交叉数来下界，这一结果本身可能很有趣。最后，我们给出了最大路径宽度图的交叉数的近似值。这是有界路径宽度的常数近似值。我们用路径宽度为 3 的图和 bicliques 的加权交叉数的 NP 硬度证明来补充这一点。
The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidth 3. The technique also shows that the crossing number and the rectilinear (a.k.a. straight-line) crossing number are identical for this graph class, and that we require only an-grid to achieve such a drawing. Our techniques can further be extended to devise a 2-approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lower-bounded using the crossing numbers of its cut-components, a result that may be interesting in its own right. Finally, we give a-approximation of the crossing number for maximal graphs of pathwidth. This is a constant approximation for bounded pathwidth. We complement this with an NP-hardness proof of theweightedcrossing number already for pathwidth 3 graphs and bicliques.
登录
查看更多内容
影响因子：
1
作者：
COURCELLE, B
通讯作者：
COURCELLE, B
图的路径宽度和树宽度的高效且有建设性的算法
DOI：
10.1006/jagm.1996.0049
发表时间：
1993
期刊：
J. Algorithms
影响因子：
--
作者：
H. Bodlaender;T. Kloks
通讯作者：
T. Kloks
DOI：
10.4230/lipics.socg.2016.30
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Markus Chimani;Petr Hliněný
通讯作者：
Petr Hliněný
交叉数临界图具有有限的路径宽度
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Petr Hliněný
通讯作者：
Petr Hliněný
交叉数的更紧密的基于插入的近似
影响因子：
1
作者：
M. Chimani;P. Hlinĕný
通讯作者：
P. Hlinĕný