A left-first search algorithm for planar graphs

We give anO(|V(G)|)-time algorithm to assign vertical and horizontal segments to the vertices of any bipartite plane graphG 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 adjacent. As a corollary, we obtain a strengthening of the following theorem of Ringel and Petrovič. The edges of any maximal bipartite plane graphG with outer facebwb′w′ can be colored by two colors such that the color classes form spanning trees ofG−b andG−b′, respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new linear-time algorithm for constructing bipolar orientations of 2-connected plane graphs. The research of H. de Fraysseix and P. O. de Mendez was supported by ESPRIT Basic Research Action No. 7141 (ALCOM II). J. Pach's research was supported by NSF Grant CCR-91-22103, OTKA-4269, and ALCOM II.