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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/670

Actions (login required)

View Item View Item