Augmenting Plane Straight-Line Graphs to Meet Parity Constraints

Aleksander Bjørn Grodt Christiansen, Linda Kleist, Irene Parada +1

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 v…