On topological aspects of orientations
De Fraysseix, Hubert ; Ossona De Mendez, Patrice
HAL, hal-00005628 / Harvested from HAL
We are concerned with two classes of planar graphs: maximal planar graphs (i.e. polyhedral graphs, triangulations) and maximal bipartite planar graphs (i.e. bipartite planar graphs with quadrilateral faces). For these graphs we consider constrained orientations with a constant indegree for the internal vertex set. We recall or prove new fundamental relations between these orientations, specific tree decompositions and bipolar orientations. In particular, these relations yield linear time computation algorithms. Using these orientations, we give a characterization of 4-connected maximal planar graphs and 3-connected planar graphs, which leads to simple line time algorithms.
Publié le : 2001-07-05
Classification:  topological graph theory,  orientation,  05C10, 05C75,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00005628,
     author = {De Fraysseix, Hubert and Ossona De Mendez, Patrice},
     title = {On topological aspects of orientations},
     journal = {HAL},
     volume = {2001},
     number = {0},
     year = {2001},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00005628}
}
De Fraysseix, Hubert; Ossona De Mendez, Patrice. On topological aspects of orientations. HAL, Tome 2001 (2001) no. 0, . http://gdmltest.u-ga.fr/item/hal-00005628/