The Plane Bipolar Orientations' Lattice
Ossona De Mendez, Patrice
HAL, hal-00008545 / Harvested from HAL
Given a biconnected graph G and an oriented edge e=(s,t) of G, a bipolar orientation based on the orientation of e (or e-bipolar orientation of G) is an acyclic orientation of the edges of G having s as a unique source and t as a unique sink. Bipolar orientations are closely related to connexity and planarity. They have been extensively used to perform graph drawing of planar graphs, upward drawings and testing graph planarity. In the planar case, the angle graphe A(G) of G is defined as the vertex/face adjacency graph related to an embedding of G. Then, the e-bipolar orientations of G are in bijection with the edge 2-colorations of A(G) satisfying local conditions. From the 2-coloration corresponding to an e-bipolar orientation, the 2-coloration corresponding to any other e-bipolar orientation may be obtained by inverting the edge coloration over alternating cycles. An edge 2-coloration of A(G) is equivalent to an orientation of the edges of A(G). When considering this orientation, alternating cycles of A(G) correspond to oriented circuits. The transformation from one e-bipolar orientation O into another e-bipolar orientation O' corresponds (in A(G)) to the inversion of a circuit. This circuit may be expressed as the sum of clockwise oriented faces of A(G) using integer coefficients. All or part of these coefficients might be negative integers. If all of them are positive, O is said to be smaller than O'. If the graph is 3-connected, the so defined partial order is a distributive lattice on the e-bipolar orientations' set of a plane graph G. That means that two uncomparable e-bipolar orientations O and O' have an infimum O/\ O' (a greatest e-bipolar orientation smaller than both O and O') and a supremum OV O'. This lattice is distributive as the infimum and supremum operators are distributive with one another. Moreover, the minimum and maximum e-bipolar orientations of the lattice may be expressed using a very simple linear-time algorithm. The Hasse diagram of the lattice, that is the graph whose vertices are the e-bipolar orientations of G and whose (oriented) edges correspond to the immediate-sucessor relation, is the adjacency graph of the e-bipolar orientations of G (two orientations being adjacent if they differ by the orientation of an unique edge) with an appropriate orientation.
Publié le : 1993-07-05
Classification:  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00008545,
     author = {Ossona De Mendez, Patrice},
     title = {The Plane Bipolar Orientations' Lattice},
     journal = {HAL},
     volume = {1993},
     number = {0},
     year = {1993},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00008545}
}
Ossona De Mendez, Patrice. The Plane Bipolar Orientations' Lattice. HAL, Tome 1993 (1993) no. 0, . http://gdmltest.u-ga.fr/item/hal-00008545/