论文标题
平面图的平面增强以满足奇偶校验约束
Plane augmentation of plane graphs to meet parity constraints
论文作者
论文摘要
平面拓扑图$ g =（v，e）$是在平面中绘制的图形，其顶点是平面中的点，其边缘是简单的曲线，除了在其端点处没有相交的简单曲线。给定平面拓扑图$ g =（v，e）$和一套$ c_g $的均等约束，其中每个顶点都在其程度上分配了奇偶校验约束，即使或奇怪，我们说$ g $ asph \ emph {topogologically上可扩增}，以满足$ c_g $，以满足$ c_g $，如果在那里$ c_g $ h.他们的联合是一个符合所有奇偶校验约束的平面拓扑图。 在本文中，我们证明了确定平面拓扑图在拓扑上是否可以增强以达到奇偶校验约束的问题是$ \ MATHCAL {NP} $ - 即使必须更改其平等的顶点是$ v $或奇怪程度的顶点。特别是，确定是否可以将平面拓扑图扩展到Eulerian平面拓扑图中是$ \ MATHCAL {NP} $ - 完整。当必须通过平面拓扑完美匹配的顶点不符合其奇偶群之间的平面拓扑完美匹配时，获得了类似的复杂性结果。 我们将这些硬度结果扩展到平面图，当增强图必须是平面并将平面几何图（边缘是直线段的平面拓扑图）（平面拓扑图）时。此外，当需要通过平面几何形状完美匹配的顶点不符合他们的平等的平面完美匹配来进行增强时，我们还证明了这种增强问题是$ \ Mathcal {np} $ - 平面几何树和路径的完整。 对于特定的最大外平面图家族，我们表征了最大外平面图，这些图是可以增强的，以满足一组奇偶校验约束。
A plane topological graph $G=(V,E)$ is a graph drawn in the plane whose vertices are points in the plane and whose edges are simple curves that do not intersect, except at their endpoints. Given a plane topological graph $G=(V,E)$ and a set $C_G$ of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we say that $G$ is \emph{topologically augmentable} to meet $C_G$ if there exits a plane topological graph $H$ on the same set of vertices, such that $G$ and $H$ are edge-disjoint and their union is a plane topological graph that meets all parity constraints. In this paper, we prove that the problem of deciding if a plane topological graph is topologically augmentable to meet parity constraints is $\mathcal{NP}$-complete, even if the set of vertices that must change their parities is $V$ or the set of vertices with odd degree. In particular, deciding if a plane topological graph can be augmented to a Eulerian plane topological graph is $\mathcal{NP}$-complete. Analogous complexity results are obtained, when the augmentation must be done by a plane topological perfect matching between the vertices not meeting their parities. We extend these hardness results to planar graphs, when the augmented graph must be planar, and to plane geometric graphs (plane topological graphs whose edges are straight-line segments). In addition, when it is required that the augmentation is made by a plane geometric perfect matching between the vertices not meeting their parities, we also prove that this augmentation problem is $\mathcal{NP}$-complete for plane geometric trees and paths. For the particular family of maximal outerplane graphs, we characterize maximal outerplane graphs that are topological augmentable to satisfy a set of parity constraints.
