Planar graphs and poset dimension (Q1121926)

If \(G=(V,E)\) is a finite simple (undirected) graph, then a poset \(G^*\) is defined on \(V\cup E\) by the relation \(a<_ Gb\) iff \(a\in V\), \(b\in E\) and \(a\in b\). dim \(G^*=(order)\)-dim G\(=(poset)\)-\(\dim G\) is the minimal number of total orders on \(V\cup E\) whose intersection is \(G^*\). The order relation \(<_ G\) provides a strong connection between graphs (as defined) and (height one) posets (such that distinct non-minimal maximal elements cover distinct doubletons). Indeed, this interesting paper is an excellent illustration of this claim. Thus, it is proven that a graph G has dim \(G^*\leq 3\) iff G is a planar graph. On the way to proving this important result in two distinct ways, other information of a more general nature is obtained as well. Using the characterization it then becomes possible to provide ``natural'' proofs of properties of planar graphs such as the property that each planar graph has arboricity at most three and that each planar graph has an embedding whose edges are straight line segments. In particular, the labeling of the vertices which results illustrates the ``naturality'' of the arguments and constructions. A short last section is concerned with the extension of general observations and some other results to hypergraphs.