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.
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.
Repository Staff Only: item control page