Premium
Posets and planar graphs
Author(s) -
Felsner Stefan,
Trotter William T.
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20081
Subject(s) - combinatorics , mathematics , outerplanar graph , planar graph , discrete mathematics , metric dimension , graph , dimension (graph theory) , pathwidth , line graph
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 K n 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