%0 Journal Article %1 Schnyder1989 %A Schnyder, Walter %D 1989 %J Order %K poset_dimension %N 4 %P 323--343 %R 10.1007/BF00353652 %T Planar graphs and poset dimension %U https://doi.org/10.1007/BF00353652 %V 5 %X We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<Gb if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V ∪ E whose intersection is <G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.

@article{Schnyder1989, abstract = {We view the incidence relation of a graph G=(V. E) as an order relation on its vertices and edges, i.e. a<Gb if and only of a is a vertex and b is an edge incident on a. This leads to the definition of the order-dimension of G as the minimum number of total orders on V ∪ E whose intersection is <G. Our main result is the characterization of planar graphs as the graphs whose order-dimension does not exceed three. Strong versions of several known properties of planar graphs are implied by this characterization. These properties include: each planar graph has arboricity at most three and each planar graph has a plane embedding whose edges are straight line segments. A nice feature of this embedding is that the coordinates of the vertices have a purely combinatorial meaning.}, added-at = {2024-04-26T19:29:16.000+0200}, author = {Schnyder, Walter}, biburl = {https://www.bibsonomy.org/bibtex/247b8fed0a2a1f22aa536ff1304702099/duerrschnabel}, day = 01, doi = {10.1007/BF00353652}, interhash = {890eef15ac03ccd73ddf72a000532cdd}, intrahash = {47b8fed0a2a1f22aa536ff1304702099}, issn = {1572-9273}, journal = {Order}, keywords = {poset_dimension}, month = dec, number = 4, pages = {323--343}, timestamp = {2024-04-26T19:29:16.000+0200}, title = {Planar graphs and poset dimension}, url = {https://doi.org/10.1007/BF00353652}, volume = 5, year = 1989 }