"I'm looking for explicit algorithm to construct contact graphs that correspond to cubic planar bipartite graphs" I suggest you use plantri http://cs.anu.edu.au/~bdm/plantri/ to generate the graphs.

represent the graphs as vertex-edge incidence matrices A
slice a row from A to get A'

multiply A' by its transpose to get the Kirchoff (or discrete Laplacian) matrix
Using kirchhoffs laws for current and voltage we get A'x = b
solving we invert K and find its determinant using LU decomposition
x is the voltage vector of the nodes, this gives the horizontal line heights

if you performed the same operation with the dual graph of the graph used to get matrix A, you would end up with the vertical line positions

multiplying A' * K^-1 * A we get the branch (or edge ) currents matrix, each row corresponds to a different set of solutions, the currents are the lengths of the horizontal line segments
and the dual graph gives the lengths of the vertical line segments

These are actually dissections of rectangles into squares, but dissections of squares into rectangles can be achieved by using outside algebraic constraints or by using a conductance matrix C A'*C*transpose(A') instead of just A*A' above

refer to electrical network theory, squared rectangles, brooks, smith , tutte & stone, kenyon, etc

Stuart Anderson