The Order Dimension of Planar Maps Revisited
The Order Dimension of Planar Maps Revisited
复制标题
重新审视平面地图的秩序维度
DOI：
10.1137/130945284
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Stefan Felsner
中科院分区：
文献类型：
--
作者：
Stefan Felsner
Schnyder用序维数刻画了平面图。用于证明的结构已经找到了许多应用。研究人员还发现了这个开创性结果的几个扩展。一个特别深远的延伸是Brightwell-特罗特定理关于平面地图。它指出平面地图的顶点、边和面的关联偏序集的序维数最多为4。原来的证明推广了施奈德路径和施奈德区域的机器。在这篇简短的论文中，我们使用一个简单的结果关于网格相交图的序维数，以显示一个稍微强一些的结果：。在这里，指的是与高度二相关的特定顺序。 Brightwell-Trotter定理如下becauseholds为每。这可能是在不使用Schnyder介绍的工具的情况下获得的第一个结果。
Schnyder characterized planar graphs in terms of order dimension. The structures used for the proof have found many applications. Researchers also found several extensions of the seminal result. A particularly far-reaching extension is the Brightwell--Trotter theorem about planar maps. It states that the order dimension of the incidence posetof vertices, edges, and faces of a planar maphas dimension at most 4. The original proof generalizes the machinery of Schnyder paths and Schnyder regions. In this short paper we use a simple result about the order dimension of grid intersection graphs to show a slightly stronger result:. Here,refers to a particular order of height two associated with. The Brightwell--Trotter theorem follows becauseholds for every. This may be the first result in the area that is obtained without using the tools introduced by Schnyder.
登录
查看更多内容
影响因子：
0.8
作者：
G. Brightwell;W. T. Trotter
通讯作者：
W. T. Trotter
位姿和平面图
影响因子：
0.9
作者：
S. Felsner;W. T. Trotter
通讯作者：
W. T. Trotter
DOI：
--
发表时间：
2003
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Nicolas Bonichon;C. Gavoille;Nicolas Hanusse
通讯作者：
Nicolas Hanusse
正交曲面及其 CP 阶
影响因子：
0.4
作者：
S. Felsner;Sarah Kappes
通讯作者：
Sarah Kappes
以最佳复杂度计算制图
影响因子：
0.8
作者：
M. J. Alam;T. Biedl;S. Felsner;M. Kaufmann;S. Kobourov;T. Ueckerdt
通讯作者：
T. Ueckerdt