论文标题
参数化的部分预言杂交编号
Parameterised Partially-Predrawn Crossing Number
论文作者
论文摘要
受到越来越流行的研究扩展部分图形图的启发，我们提出了有关传统且最重要的几何图参数，即交叉数字的新观点。具体而言，我们将部分偏见的交叉数定义为任何图的任何图形中的最小交叉数，其中一部分是在输入上的（不计算规定的交叉点）。我们的主要结果 - 计算部分偏见的杂交数的FPT -Algorithm-结合了对经典交叉数字的研究的高级思想，并以非常自然但复杂的方式称为部分平面。我们的技术不仅通过Grohe概括了已知的FPT-Algorithm来计算标准交叉数量，而且还使我们可以大大改善各种图形扩展问题的最新参数化结果。
Inspired by the increasingly popular research on extending partial graph drawings, we propose a new perspective on the traditional and arguably most important geometric graph parameter, the crossing number. Specifically, we define the partially predrawn crossing number to be the smallest number of crossings in any drawing of a graph, part of which is prescribed on the input (not counting the prescribed crossings). Our main result - an FPT-algorithm to compute the partially predrawn crossing number - combines advanced ideas from research on the classical crossing number and so called partial planarity in a very natural but intricate way. Not only do our techniques generalise the known FPT-algorithm by Grohe for computing the standard crossing number, they also allow us to substantially improve a number of recent parameterised results for various drawing extension problems.
