show/hide this revision's text 2 added 473 characters in body; added 1 characters in body

Any planar graph can be drawn with curves for the edges and its vertices in any position in the plane.

But with straight line segment edges, it's not always possible, even for graphs in which every vertex in A has degree exactly two, and even if you relax the straight-line requirement for A and only require that the vertices in B be on a straight line. For, these graphs are exactly the graphs formed by subdividing every edge of an arbitrary planar graph G. And a drawing of this type, for a graph formed from G in this way, is exactly a two-page book embedding of G. But a planar graph G has a two-page book embedding only if edges can be added to it to make it Hamiltonian. So if you start with a graph G that is maximal planar and non-Hamiltonian, such as the Goldner–Harary graph, and subdivide every edge, you will get a planar bipartite graph that cannot be drawn in the way you request.

As an aside, relaxing the requirement that A be drawn on two lines parallel to the line through B does allow some additional graphs to be drawn, even though the above argument shows that it doesn't allow them all. For instance, Louigi has shown that the cube has no drawing on three parallel lines, but it does have one where B is on a straight line and A is on two sides of it:

alt text

show/hide this revision's text 1

Any planar graph can be drawn with curves for the edges and its vertices in any position in the plane.

But with straight line segment edges, it's not always possible, even for graphs in which every vertex in A has degree exactly two, and even if you relax the straight-line requirement for A and only require that the vertices in B be on a straight line. For, these graphs are exactly the graphs formed by subdividing every edge of an arbitrary planar graph G. And a drawing of this type, for a graph formed from G in this way, is exactly a two-page book embedding of G. But a planar graph G has a two-page book embedding only if edges can be added to it to make it Hamiltonian. So if you start with a graph G that is maximal planar and non-Hamiltonian, such as the Goldner–Harary graph, and subdivide every edge, you will get a planar bipartite graph that cannot be drawn in the way you request.