Posets and planar graphs
Stefan Felsner, William T. Trotter · Journal of Graph Theory · 2005
Abstract Usually dimension should be an integer valued parameter. We introduce a refined version of dimension for graphs, which can assume a value [t − 1 ↕ t], thought to be between t − 1 and t. We have the following two results: (a) a graph is outerplanar if and only if its dimension is at most [2↕3]. This characterization of outerplanar graphs is closely related to the celebrated result of W. Schnyder [16] who proved that a graph is planar if and only if its dimension is at most 3. (b) The largest n for which the dimension of the complete graph Kn is at most [t − 1 ↕ t] is the number of antichains in the lattice of all subsets of a set of size t − 2. Accordingly, the refined dimension problem for complete graphs is equivalent to the classical combinatorial problem known as Dedekind's problem. This result extends work of Hoşten and Morris [14]. The main results are enriched by background material, which links to a line of research in extremal graph theory, which was stimulated by a problem posed by G. Agnarsson: Find the maximum number of edges in a graph on n nodes with dimension at most t. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 273–284, 2005