A LeftFirst Search Algorithm for Planar GraphsDe Fraysseix, Hubert and Ossona de Mendez, Patrice and Pach, János (1995) A LeftFirst Search Algorithm for Planar Graphs. [Journal (Paginated)] Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BF02574056
AbstractWe 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, (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 Petrovic. The edges of any maximal bipartite plane graph G with outer face bwb'w' can be colored by two colors such that the color classes form spanning trees of Gb and Gb', respectively. Furthermore, such a coloring can be found in linear time. Our method is based on a new lineartime algorithm for constructing bipolar orientations of 2connected plane graphs.
Actions (login required)
