Planarity and Edge Poset Dimension
De Fraysseix, Hubert ; Ossona De Mendez, Patrice
HAL, hal-00005624 / Harvested from HAL
Different areas of discrete mathematics lead to instrinsically 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 of 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.
Publié le : 1996-07-05
Classification:  graph theory,  poset dimension,  planarity,  bipolar orientation,  05C10,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{hal-00005624,
     author = {De Fraysseix, Hubert and Ossona De Mendez, Patrice},
     title = {Planarity and Edge Poset Dimension},
     journal = {HAL},
     volume = {1996},
     number = {0},
     year = {1996},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00005624}
}
De Fraysseix, Hubert; Ossona De Mendez, Patrice. Planarity and Edge Poset Dimension. HAL, Tome 1996 (1996) no. 0, . http://gdmltest.u-ga.fr/item/hal-00005624/