Inserting Multiple Edges into a Planar Graph
Inserting Multiple Edges into a Planar Graph
复制标题
将多条边插入平面图
DOI：
10.4230/lipics.socg.2016.30
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Petr Hliněný
中科院分区：
文献类型：
--
作者：
Markus Chimani;Petr Hliněný
设$G$是一个连通的平面图（但还没有嵌入），$F$是一组还没有在$G$中的附加边。多重边插入问题（MEI）要求$G+F$的一个图具有最少的成对边交叉数，使得$G$的子图是平面的。这个问题的最优解近似于图$G+F$的交叉数。
对于一般的F$，求MEI的精确解是NP困难的，但对于特殊的F $，则是线性时间可解的|F| =1$（SODA 01，migica）或当所有$F$都关联到新顶点（SODA 09）时。
一般的$F$的复杂性，但具有常数$k=| F| $是开放的，但是已经提出了具有相对和绝对近似保证的算法（SODA 11，ICALP 11）。我们表明，问题是固定参数易处理（FPT）在$k$的双连通的$G$，或如果$G$的割顶点有一定程度的常数有界。我们给出了这个问题的第一个精确算法;它只需要O（|V（G）|）$时间对于任何常数$k$。
Let $G$ be a connected planar (but not yet embedded) graph and $F$ a set of additional edges not yet in $G$. The {multiple edge insertion} problem (MEI) asks for a drawing of $G+F$ with the minimum number of pairwise edge crossings, such that the subdrawing of $G$ is plane. An optimal solution to this problem approximates the crossing number of the graph $G+F$.
Finding an exact solution to MEI is NP-hard for general $F$, but linear time solvable for the special case of $|F|=1$ (SODA01, Algorithmica) or when all of $F$ are incident to a new vertex (SODA09).
The complexity for general $F$ but with constant $k=|F|$ was open, but algorithms both with relative and absolute approximation guarantees have been presented (SODA11, ICALP11). We show that the problem is fixed parameter tractable (FPT) in $k$ for biconnected $G$, or if the cut vertices of $G$ have degrees bounded by a constant. We give the first exact algorithm for this problem; it requires only $O(|V(G)|)$ time for any constant $k$.
交叉数的更紧密的基于插入的近似
影响因子：
1
作者：
M. Chimani;P. Hlinĕný
通讯作者：
P. Hlinĕný
DOI：
10.1016/j.ejc.2011.09.009
发表时间：
2012
期刊：
Eur. J. Comb.
影响因子：
--
作者：
Markus Chimani;Petr Hliněný;Petra Mutzel
通讯作者：
Petra Mutzel