A Left-First Search Algorithm for Planar Graphs.
De Fraysseix, Hubert ; Ossona De Mendez, Patrice ; Pach, Janos
HAL, hal-00005623 / Harvested from HAL
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, (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 G-b and G-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.
Publié le : 1995-07-05
Classification:  05C62, 05C85,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00005623,
     author = {De Fraysseix, Hubert and Ossona De Mendez, Patrice and Pach, Janos},
     title = {A Left-First Search Algorithm for Planar Graphs.},
     journal = {HAL},
     volume = {1995},
     number = {0},
     year = {1995},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00005623}
}
De Fraysseix, Hubert; Ossona De Mendez, Patrice; Pach, Janos. A Left-First Search Algorithm for Planar Graphs.. HAL, Tome 1995 (1995) no. 0, . http://gdmltest.u-ga.fr/item/hal-00005623/