论文标题
在多项式时间内延长几乎完整的1平面图
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
论文作者
论文摘要
近年来，扩展部分几何图表示（例如平面图）的问题受到了广泛关注。特别是，给定图形$ g $，$ g $的连接子图$ h $和$ h $的图形$ \ mathcal {h} $ of $ h $，扩展问题询问是否可以将$ \ mathcal {h} $扩展到$ g $的图纸的同时，同时维持图纸的某些所需属性（例如，平面图）。 在他们的突破结果中，Angelini等人。 [ACM TALG 2015]表明，当目的是保持平面度时，扩展问题是多项式时间的溶解。最近，我们考虑了部分1平面图的问题[ICARP 2020]，它们是平面中的图纸，使每个边缘最多都有一个交叉。在这项工作中确定和打开的最重要的问题是，当$ h $可以通过删除有限数量的顶点和边缘从$ g $获得$ h $时，是否可以在多项式时间内解决问题。在这项工作中，我们通过提供建设性的多项式决策算法来积极回答这个问题。
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph $G$, a connected subgraph $H$ of $G$ and a drawing $\mathcal{H}$ of $H$, the extension problem asks whether $\mathcal{H}$ can be extended into a drawing of $G$ while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when $H$ can be obtained from $G$ by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm.
