首页> 外文期刊>SIAM Journal on Discrete Mathematics >UPPER BOUND CONSTRUCTIONS FOR UNTANGLING PLANAR GEOMETRIC GRAPHS
【24h】

UPPER BOUND CONSTRUCTIONS FOR UNTANGLING PLANAR GEOMETRIC GRAPHS

机译:纠缠平面几何图形的上界构造

获取原文
获取原文并翻译 | 示例
       

摘要

For every n ∈ N, we construct an n-vertex planar graph G = (V, E) and n distinct points p(v), v ∈ V, in the plane such that in any crossing-free straight-line drawing of G, at most O(n~(.4948)) vertices v ∈ V are embedded at points p(v). This improves on an earlier bound of O(n~(1/2)) by Goaoc et al. [Discrete Comput. Geom., 42 (2009), pp. 542-569].
机译:对于每个n∈N,我们构造一个n顶点平面图G =(V,E)并在该平面中构造n个不同的点p(v),v∈V,使得在G的任何无交叉直线图中,最多在点p(v)上嵌入O(n〜(.4948))个顶点v∈V。 Goaoc等人在O(n〜(1/2))的更早界限上进行了改进。 [离散计算。 Geom。,42(2009),542-569页]。

著录项

  • 来源
    《SIAM Journal on Discrete Mathematics》 |2014年第4期|1935-1943|共9页
  • 作者单位

    Posgrado en Ciencia e Ingenieria de la Computacion, Universidad Nacional Autonoma de Mexico, Coyoacan, D.F. Mexico;

    Department of Mathematics, California State University Northridge, Los Angeles, CA 91330, and Department of Computer Science, Tufts University, Medford, MA 02155;

    Instituto de Matematicas, Universidad Nacional Autonoma de Mexico, Coyoacan, D.F. Mexico;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    geometric graph; planar graph; untangling; Erdoes-Szekeres theorem;

    机译:几何图平面图解开Erdoes-Szekeres定理;
  • 入库时间 2022-08-18 03:02:08

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号