Space-efficient acyclicity constraints: A declarative pearl

In this paper, we show how to refine this encoding into one that uses only a single bit of information, i.e. a 2-valued variable, per vertex, assuming the graph in question is planar. More generally, for graphs that are embeddable in genus g (i.e. on a torus with g handles), we show that 2g+1 bits per vertex suffices. We furthermore show how this same constraint can be used to encode connectedness constraints, and a variety of other graph-related constraints.