Plane augmentation of plane graphs to meet parity constraints

Highlights：

• Given a plane topological graph and a set of parity constraints, in which every vertex has assigned a parity constraint on its degree, either even or odd, we study the problem of adding new edges to the graph such that the resulting graph is plane and meets all parity constraints.

• We show the NP-completeness of this problem for several variants that depend on the graph class, and the vertices that must change their parities. We extend these results to planar graphs and to plane geometric graphs.

• We also show that the problem of deciding if a plane topological (geometric) graph can be augmented to a Eulerian plane topological (geometric) graph is NP-complete.

• For the family of maximal outerplane graphs, we characterize maximal outerplane graphs that are topologically augmentable to meet a set of parity constraints, and we provide an O(n3) algorithm to find a minimum augmentation if it exists.