• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph Drawing; Lecture Notes in Computer Science; 4372 >Schnyder Woods and Orthogonal Surfaces
【24h】

Schnyder Woods and Orthogonal Surfaces

机译：施耐德森林与正交曲面

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory. Orthogonal surfaces explain the connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says that the face lattice of a 3-polytope minus one face has dimension three. Our proof yields a companion linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondance with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder's face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.
机译：在本文中，我们研究Schnyder木材与正交曲面之间的连接。 Schnyder Woods和人脸计数方法在图形绘制和尺寸理论中具有重要的应用。正交曲面解释了这些看似无关的概念之间的联系。我们使用这些连接来直观地证明Brightwell-Trotter定理，该定理表示3多边形减去一个面的面格的尺寸为3。我们的证明产生了一个伴随线性时间算法，用于构造实现面部晶格的三个线性阶次。共面正交表面与3个连接的平面图的一大类凸直线图相对应。我们证明了Schnyder的带有加权面的面计数方法可用于构造所有共面正交面，从而构造相应的图形。可以在线性时间内计算适当的权重。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号