Planarity and edge poset dimension

De Fraysseix, Hubert and Ossona de Mendez, Patrice (1997) Planarity and edge poset dimension. [Journal (Paginated)]

Full text not available from this repository.

Abstract

Different areas of discrete mathematics lead to intrinsically different characterizations of planar graphs. Planarity is expressed in terms of topology, combinatorics, algebra or search trees. More recently, Schnyder's work has related planarity to partial order theory. Acyclic orientations and associated edge partial orders lead to a new characterization of planar graphs, which also describes all the possible planar embeddings. We prove here that there is a bijection between bipolar plane digraphs and 2-dimensional N-free partial orders. We give also a characterization of planarity in terms of 2-colorability of a graph and provide a short proof of a previous result on planar lattices.

Item Type:Journal (Paginated)
Additional Information:10.1006/eujc.1996.0064
Classifications:Z Theory > Z.001 General
ID Code:670

Repository Staff Only: item control page

References

K.A. Baker, P. Fishburn, and F.S. Roberts. Partial orders of dimension 2. Networks, 2:11-28, 1971.

G. Birkhoff. Lattice Theory. American Mathematical Society, 1967. Troisième édition.

H. de Fraysseix and P. O. de Mendez. A characterization of graphic oriented matroids. in preparation.

H. de Fraysseix, P. O. de Mendez, and J. Pach. A streamlined depth-first search algorithm revisited. Technical report, ALCOM-II-030, 1993.

H. de Fraysseix, P. O. de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. In Fifth Franco-Japanese Days on Combinatorics and Optimization, 1992.

H. de Fraysseix and Rosenstiehl P. A characterization of planar graphs by Trémaux orders. Combinatorica, 5(2):127-135, 1985.

H. de Fraysseix, J. Pach, and R. Pollack. Small sets supporting Fary embeddings of planar graphs. In Twentieth Annual ACM Symposium on Theory of Computing, pages 426-433, 1988.

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

J. Edmonds. A combinatorial representation for polyhedral surfaces. Notices of American Mathematical Society, 7:643, 1960.

S. Even and R.E. Tarjan. Computing an st-numbering. Theroretical Computer Science, 2:339-344, 1976.

A. Ghouila-Houri. Caract?erisation des graphes non orient?es dont on peut orienter les arêtes de manière à obtenir le graphe d'une relation d'ordre. Compte rendu de l'Academie des Sciences, 254:1370-1371, 1962.

P.C. Gilmore and A.J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964.

M. Habib and R.H. M@@ohring. On some complexity properties of N-free posets with bounded decomposition diameter. Discrete Mathematics, 63:157-182, 1987.

D. Kelly and I. Rival. Planar lattices. Canadian Jounal of Mathematics, 27:636-665, 1975.

M. Las Vergnas. Sur la dualit?e en th?eorie des matroides. Lecture Notes in Mathematics, 211:67-85, 1970.

B. Leclerc and B. Monjardet. Ordres "C.A.C.". Fundamenta Mathematicae, 8:11-22, 1973.

S. Mac Lane. A combinatorial condition for planar graphs. Fund. Math., 28:22-32, 1937.

P. Ossona de Mendez. Orientations bipolaires. PhD thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1994.

C.R. Platt. Planar lattices and planar graphs. Journal of combinatorial geometry, 21:30-39, 1976.

P. Rosenstiehl and R.E. Tarjan. Rectilinear planar layout and bipolar orientation of planar graphs. Discrete and Computational Geometry, 1:343-353, 1986.

W. Schnyder. Planar graphs and poset dimension. Order, 5:323-343, 1989.

W.T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45-53, 1970.

H. Whitney. Planar graphs. Fund. Math., 21:73-84, 1933.