We give an O(\V(G)\)-time algorithm to assign vertical and horizontal
segments to the vertices of any bipartite plane graph G so that (i) no
two segments have an interior point in common, and (ii) two segments
touch each other if and only if the corresponding vertices are adjacen
t. As a corollary, we obtain a strengthening of the following theorem
of Ringel and Petrovic. The edges of any maximal bipartite plane graph
G with outer face bwb'w' can be colored by two colors such that the c
olor classes form spanning trees of G - b and G - b', respectively. Fu
rthermore, such a coloring can be found in linear time. Our method is
based on a new linear-time algorithm for constructing bipolar orientat
ions of 2-connected plane graphs.