Oswin Aichholzer, Thomas Hackl, Michael Hoffmann, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber:

Plane graphs with party constraints

1. In: Algorithms and Data Structures Symposium—WADS 2009, Banff, August 2009, Editors: Frank Dehne, Ian Munro, Jörg-Rüdiger Sack, and Roberto Tamassia, Lecture Notes in Computer Science, 5664, Springer-Verlag, 2009, pp. 13–24. doi:10.1007/978-3-642-03367-4_2
2. Graphs and Combinatorics 30 (2014), 47–69. doi:10.1007/s00373-012-1247-y

Abstract

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.