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.
%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
}