Augmenting Plane Straight-Line Graphs to Meet Parity Constraints
摘要
Given a plane geometric graph G on n vertices, we want to augment it so that given parity constraints of the vertex degrees are met. In other words, given a subset R of the vertices, we are interested in a plane geometric supergraph \(G'\) such that exactly the vertices of R have odd degree in \(G'\setminus G\) . We show that the question of whether such a supergraph exists can be decided in polynomial time for two interesting cases. First, when the vertices are in convex position, we present a linear-time algorithm. Building on this insight, we solve the case when G is a plane geometric path in \(O(n \log n)\) time. This solves an open problem posed by Catana, Olaverri, Tejel, and Urrutia (Appl. Math. Comput. 2020).