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′ \ G. We show that the question 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).