首页> 外文期刊>Graphs and Combinatorics >On the Number of Plane Geometric Graphs
【24h】

On the Number of Plane Geometric Graphs

机译:关于平面几何图的数量

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

摘要

We investigate the number of plane geometric, i.e., straight-line, graphs, a set S of n points in the plane admits. We show that the number of plane geometric graphs and connected plane geometric graphs as well as the number of cycle-free plane geometric graphs is minimized when S is in convex position. Moreover, these results hold for all these graphs with an arbitrary but fixed number of edges. Consequently, we provide a unified proof that the cardinality of any family of acyclic graphs (for example spanning trees, forests, perfect matchings, spanning paths, and more) is minimized for point sets in convex position.
机译:我们研究平面几何图形的数量,即直线图,平面中n点的一组S.我们表明,当S处于凸位置时,平面几何图和连接的平面几何图的数量以及无循环平面几何图的数量最小。此外,这些结果适用于所有这些具有任意但固定数量的边的图。因此,我们提供了一个统一的证明,即对于凸位置上的点集,任何非循环图族(例如,跨越树木,森林,完美匹配,跨越路径等等)的基数都最小。

著录项

  • 来源
    《Graphs and Combinatorics》 |2007年第s1期|67-84|共18页
  • 作者单位

    Institute for Software Technology Graz University of Technology Graz Austria;

    Institute for Software Technology Graz University of Technology Graz Austria;

    Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona Spain;

    Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona Spain;

    Institute for Theoretical Computer Science Graz University of Technology Graz Austria;

    Institute for Software Technology Graz University of Technology Graz Austria;

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

  • 入库时间 2022-08-18 01:49:08

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号