• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Closed Rectangle-of-Influence Drawings for Irreducible Triangulations
【24h】

Closed Rectangle-of-Influence Drawings for Irreducible Triangulations

机译：不可约三角剖分的封闭影响矩形图

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

摘要

A closed rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel rectangle defined by the two end vertices of any edge. Biedl et al. [2] showed that a plane graph G has a closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a closed RI drawing in an (n - 1) x (n - 1) grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved [2]. Without loss of generality, we investigate maximal plane graphs admitting closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7]. In this paper, we present a linear time algorithm that computes closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a closed RI drawing with size at most (n -3) × (n - 3); and for a random irreducible triangulation, the expected grid size of the drawing is (22n/27 + O(n~(?)) × (22n/27 + O(n~(?)). We then prove that for arbitrary n > 4, there is an n-vertex irreducible triangulation, such that any of its closed RI drawing requires a grid of size (n - 3) × (n - 3). Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in [2] negatively.
机译：闭合影响矩形图（RI）是一个直线网格图，其中在任何边缘的两个末端顶点所定义的轴平行矩形的内部或边界上没有其他顶点。 Biedl等。 [2]表明，当且仅当平面图G没有填充的3周期（3个顶点的周期，使得在适当的内部存在一个顶点）时，该图形G才具有封闭的RI图。他们还表明，这样的图G在（n-1）x（n-1）网格中具有闭合的RI图，其中n是G中的顶点数。他们提出了一个开放的问题，即该网格大小范围是否可以有待改进[2]。在不失一般性的前提下，我们研究了允许封闭RI图的最大平面图。它们是具有四边形外表面，三角形内表面且没有填充的3个环的平面图，称为不可约三角剖分[7]。在本文中，我们提出了一种线性时间算法，该算法计算不可约三角剖分的封闭RI图。给定具有n个顶点的任意不可约三角剖分G，我们的算法将生成一个封闭的RI图，其大小最大为（n -3）×（n-3）；对于随机不可约三角剖分，图形的预期网格大小为（22n / 27 + O（n〜（？））×（22n / 27 + O（n〜（？））。然后证明对于任意n > 4，存在一个n顶点不可约的三角剖分，因此其任何封闭的RI绘图都需要一个（n-3）×（n-3）大小的网格，因此，由我们的算法生成的绘图的网格大小是紧密的这个下限也否定地回答了[2]中提出的开放性问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号