Bipolar orientations revisited

De Fraysseix, Hubert and Ossona de Mendez, Patrice and Rosenstiehl, Pierre (1995) Bipolar orientations revisited. [Journal (Paginated)]

Full text not available from this repository.

Abstract

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.

Item Type:Journal (Paginated)
Additional Information:10.1016/0166-218X(94)00085-R
Classifications:Z Theory > Z.001 General
ID Code:668

Repository Staff Only: item control page

References

K.A. Baker, P. Fishburn and F.S. Roberts, Partial orders of dimension 2, Networks 2 (1971) 1l-28.

C. Berge, Graphes (Gauthier-Villars, Paris, troisieme edition, 1983).

G. Birkhoff, Lattice Theory (American Mathematical Society, Providence,RI, troisieme edition, 1967).

R.G. Bland and M. Las Vergnas, Orientability of matroids, J. Combin. Theory Ser. B 23 (1978) pp. 94-123.

M. Bousset, Orientation d’un schema par passage d’un flot dans les angles, Ph.D. Thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris (1993).

H. de Fraysseix and P.O. de Mendez, Planarity and edge poset dimension, European J. Combin., to appear.

H. de Fraysseix, P.O. de Mendez and J. Path, A streamlined depth-first search algorithm revisited, Technical Report, ALCOM-II-030 (1993).

H. de Fraysseix, P.O. de Mendez and J. Path, Representation of planar graphs by segments, Intuitive Geom., to appear.

H. de Fraysseix, P.O. de Mendez and P. Rosenstiehl, On triangle contact graphs, in: Proceedings Cambridge Combinatorial Conference in honor of Paul Erdos (1993).

H. de Fraysseix, J. Path and R. Pollack, Small sets supporting Fary embeddings of planar graphs, in: 20th Annual ACM Symposium on Theory of Computing (1988) 4266433.

P.O. de Mendez, Orientations bipolaires, Ph. D. Thesis, Ecole des Hautes Etudes en Sciences Sociales,Paris (1994).

G. Di Battista, P. Eades, R. Tamassia and LG. Tollis, Algorithms for automatic graph drawing: An annotated bibliography, Technical Report, Department of Computer Science, Brown University (1993).

G. Di Battista and R. Tamassia, Algorithms for plane representations of acyclic digraphs, Theoret.Comput. Sci. 61 (1988) 4366441.

G. Di Battista, R. Tamassia and I.G. Tollis, Area requirement and symmetry display of planar upward drawings, Discrete Comput. Geom. 7 (1992) 381-401.

B. Dushnik and E.W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941) 600-610.

S. Even and R.E. Tarjan, Computing an St-numbering, Theoret. Comput. Sci. 2 (1976) 339-344.

C. Greene and T. Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-random partitions, and orientations of graphs, Trans. Amer. Math. Sot. 280 (1983) 977126.

P.A. Grillet, Maximal chains and antichains, Fund. Math. 63 (65) (1969) 1577167.

F. Harary, Graph Theory (Addison-Wesley,Reading, MA, 1969).

G. Kant, Algorithms for drawing planar graphs, Ph. D. Thesis, Utrecht University, Utrecht (1993).

D. Kelly and 1. Rival, Planar lattices, Canad. J. Math. 27(3) (1975) 636-665.

M. Las Vergnas, Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Math. 20 (1977) 51-61.

B. Leclerc and B. Monjardet, Ordres “C.A.C.“, Fund. Math. 8 (1973) 1 l-22.

A. Lempel, S. Even and I. Cederbaum, An algorithm for planarity testing of graphs, in: Gordon and Breach, eds., Theory of Graphs (1967) 215-232.

A. Machi, Orientations of planar graphs with condition on the angles, Internal Report of the L.I.T.P (1992).

Y. Maon, B. Schieber and U. Vishkin, Parallel ear decomposition search (eds) and St-numbering in graphs, Theoret. Comput. Sci. 47 (1986) 277-298.

G.J. Minty, On the axiomatic foundations of the theories of directed linear graphs, electrical networks

and network programming, J. Math. Mech. 15 (1966) 4855520.

C.R. Platt, Planar lattices and planar graphs, J. Combin. Geom. 21 (1976) 30-39.

P. Rosenstiehl, Embedding in the plane with orientation constraints: the angle graph, Ann. New York Acad. Sci. (1983) 340-346.

R. Rosenstiehl, Flot sur les angles et orientations d’une carte, Technical Report LITP 92.80 (1992).

P. Rosenstiehl and R.E. Tarjan, Rectilinear planar layout and bipolar orientation of planar graphs,Discrete Comput. Geom. I (1986) 3433353.

J.P. Roudneff, Inseparability graphs of oriented matroids, Combinatorics 9 (1989) 75-84.

R. Tamassia and I.G. Tollis, A unified approach to visibility representations of planar graphs, Discrete Comput. Geom. 1 (1986) 321-341.

R. Tamassia and J.S. Vitter, Parallel transitive closure and point location in planar structures, SIAM J. Comput. 20(4) (1991) 708-725.

R.E. Tarjan, Two streamlined depth-first-search algorithms, Fund. Inform. 9 (1986) 85-94.

W.T. Trotter, Combinatorics and Partially Ordered Sets (Johns Hopkins University Press, London, 1992).

W.T. Tutte, Graph Theory, Encyclopedia of Mathematics and its Applications 21 (Addison-Wesley,Reading, MA, 1984).

D. Woods, Drawing planar graphs, Ph. D. thesis, Stanford University, Technical Report STAN-CS-82-943 (1982).