| Article ID: | iaor1996273 |
| Country: | Netherlands |
| Volume: | 56 |
| Issue: | 2/3 |
| Start Page Number: | 157 |
| End Page Number: | 179 |
| Publication Date: | Jan 1995 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Fraysseix Hubert de, Ossona de Mendez Patrice, Rosenstiehl Pierre |
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.