The math of hill-and-valley weaving

A weaving pattern for any graph drawn on a surface can be derived by taking the medial of the graph, a construction that fills the rhombic domain of each edge in the graph with black and white regions as below, (original edge in red, original vertices in green):

That construction suffices for ordinary weaving, but not for hill-and-valley texturing because the black regions, which correspond to the locations of the original vertices, must be partitioned into alternating hills and valleys. So we need to start with a bipartite graph (for example, see below: each edge connects a green vertex to a blue vertex), then the medial will inherit the needed bipartition of the black regions into hills and valleys from the bipartition of the original vertices.