• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Order >Upward Three-Dimensional Grid Drawings of Graphs
【24h】

Upward Three-Dimensional Grid Drawings of Graphs

机译：图的向上三维网格图

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

摘要

A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line segments representing the edges do not cross. Our aim is to produce three-dimensional grid drawings with small bounding box volume. Our first main result is that every n-vertex graph with bounded degeneracy has a three-dimensional grid drawing with O (n~(3/2)) volume. This is the largest known class of graphs that have such drawings. A three-dimensional grid drawing of a directed acyclic graph (dag) is upward if every arc points up in the z-direction, We prove that every dag has an upward three-dimensional grid drawing with O (n~3) volume, which is tight for the complete dag. The previous best upper bound was O (n~4). Our main result concerning upward drawings is that every c-colourable dag (c constant) has an upward three-dimensional grid drawing with O (n~2) volume. This result matches the bound in the undirected case, and improves the best known bound from O (n~3) for many classes of dags, including planar, series parallel, and outerplanar. Improved bounds are also obtained for tree dags. We prove a strong relationship between upward three-dimensional grid drawings, upward track layouts, and upward queue layouts. Finally, we study upward three-dimensional grid drawings with bends in the edges.
机译：图形的三维网格图是将顶点放置在具有整数坐标的不同点上，这样代表边缘的直线段不会交叉。我们的目标是制作具有较小边界框体积的三维网格图。我们的第一个主要结果是每个有界退化的n个顶点图都有一个三维网格图，其体积为O（n〜（3/2））。这是具有此类绘图的最大已知图形类别。如果每个圆弧都指向z方向，则有向无环图（dag）的三维网格图是向上的。我们证明每个dag都有一个向上的三维网格图，其体积为O（n〜3），其中对于完整的dag是紧的。先前的最佳上限是O（n〜4）。我们有关向上绘制的主要结果是，每个c着色dag（c常数）都有一个向上的三维网格图，其体积为O（n〜2）。此结果与无向情况下的边界匹配，并且针对许多类别的dag，包括平面，串联平行和外平面，从O（n〜3）改善了最著名的边界。对于树dags也获得了改进的边界。我们证明了向上的三维网格图形，向上的轨道布局和向上的队列布局之间的密切关系。最后，我们研究了边缘弯曲的向上三维网格图。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号