Let S be a set of n points in general position in the plane. For each point of S we are given a parity constraint, telling whether it should be even or odd. We study how well such constraints can be satisfied by various classes of planar graphs on S. Specifically, we show that we can always find a plane tree, a two-connected outerplanar graph, or a pointed pseudotriangulation that satisfies all but at most three parity constraints. With triangulations, we can satisfy about 2/3 of all parity constraints.
For a polygon with holes, it is NP-complete to decide whether it has a triangulation that satisfies all parity constraints on the vertices.
Last update: August 15, 2017.