Partial orders for planarity and drawings (abstract)
Hubert de Fraysseix, Pierre Rosenstiehl · ACM SIGACT News · 1993
A bipolar orientation of a graph appears often in the algorithm literature as a first step for the generation of a particular drawing. Here the properties of bipolar orientations are systematically explored in terms of circuits, cocircuits, rank activities, Tutte polynomial, poset dimension, angle bipartition and max flow-min cut theorem. Efficient algorithms are described to list, generate or extend bipolar orientations for general graphs or plane ones, with or without constraints. (Joint work with Patrice de Mendez.)