Scholarlink

<p>A <i>complete geometric graph</i> consists of a set <i>P</i> of <i>n</i> points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(c&lt;1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>&lt;</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, such that every complete geometric graph on <i>n</i> points can be partitioned into at most <i>cn</i> plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set <i>P</i> is <i>dense</i>, which means that the ratio between the maximum and the minimum distances in <i>P</i> is of the order of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\Theta (\sqrt{n})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Θ</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Partitioning Complete Geometric Graphs on Dense Point Sets into Plane Subgraphs

  • 期刊论文

  • 发表日期：

    2025年12月17日

查看全文
  • Adrian Dumitrescu,
  • János Pach

摘要

A complete geometric graph consists of a set P of n points in the plane, in general position, and all segments (edges) connecting them. It is a well known question of Bose, Hurtado, Rivera-Campo, and Wood, whether there exists a positive constant \(c<1\) c < 1 , such that every complete geometric graph on n points can be partitioned into at most cn plane graphs (that is, noncrossing subgraphs). We answer this question in the affirmative in the special case where the underlying point set P is dense, which means that the ratio between the maximum and the minimum distances in P is of the order of \(\Theta (\sqrt{n})\) Θ ( n ) .