Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling

MIT Hardness Group, Zachary Abel, Erik D. Demaine +3

Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? Th…