Posets and planar graphs
Posets and planar graphs
复制标题
位姿和平面图
DOI：
--
复制
发表时间：
2005
影响因子：
0.9
通讯作者：
W. T. Trotter
中科院分区：
文献类型：
--
作者：
S. Felsner;W. T. Trotter
通常情况下，维度应该是整数值参数。我们给出了图的维度的一个精化形式，它可以假定一个值[t − 1↕t]，它被认为是介于t − 1和t之间的。我们得到了以下两个结果：(A)一个图是外平面的当且仅当它的维度至多为[2↕3]。外平面图的这种刻画与W.Schnyder[16]的著名结果密切相关，他证明了一个图是平面图当且仅当它的维度至多为3。(B)完全图Kn的维度至多为[t − 1↕t]的最大n是大小为t − 2的所有子集的格中的反链的个数。因此，完全图的精维问题等价于经典的组合问题，称为Dedekind问题。这一结果推广了HoşTen和Morris[14]的工作。主要结果得到了背景材料的丰富，这些材料链接到极值图论的一系列研究，该研究受到G.Agnarsson提出的一个问题的启发：在n个结点上找到最大边数t。
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