  Motivated by the bijection between Schnyder labelings of a plane
triangulation and partitions of its inner edges into three trees, we look for
binary labelings for quadrangulations (whose edges can be partitioned into two
trees). Our labeling resembles many of the properties of Schnyder's one for
triangulations: Apart from being in bijection with tree decompositions, paths
in these trees allow to define the regions of a vertex such that counting faces
in them yields an algorithm for embedding the quadrangulation, in this case on
a~2-book. Furthermore, as Schnyder labelings have been extended to 3-connected
plane graphs, we are able to extend our labeling from quadrangulations to a
larger class of 2-connected bipartite graphs. Finally, we propose a binary
labeling for Laman graphs.
