Bipolar orientations revisited.
De Fraysseix, Hubert ; Ossona De Mendez, Patrice ; Rosenstiehl, Pierre
HAL, hal-00005622 / Harvested from HAL
Acyclic orientations with exactly one source and one sink - the so-called bipolar orientations - arise in many graph algorithms and specially in graph drawing. The fundamental properties of these orientations are explored in terms of circuits, cocircuits and also in terms of ``angles'' in the planar case. Classical results get here new simple proofs; new results concern the extension of partial orientations, exhaustive enumerations, the existence of deletable and contractable edges, and continuous transitions between bipolar orientations.
Publié le : 1995-07-05
Classification:  graph theory,  bipolar orientation,  05C20,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00005622,
     author = {De Fraysseix, Hubert and Ossona De Mendez, Patrice and Rosenstiehl, Pierre},
     title = {Bipolar orientations revisited.},
     journal = {HAL},
     volume = {1995},
     number = {0},
     year = {1995},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00005622}
}
De Fraysseix, Hubert; Ossona De Mendez, Patrice; Rosenstiehl, Pierre. Bipolar orientations revisited.. HAL, Tome 1995 (1995) no. 0, . http://gdmltest.u-ga.fr/item/hal-00005622/