Scholarlink

<p>In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and <i>n</i> additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation <i>T</i> and a point set <i>S</i> such that <i>T</i> can be drawn on <i>S</i> in at least <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varOmega (1,31^n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Ω</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <msup> <mn>31</mn> <mi>n</mi> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.</p>

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

On the Number of Drawings of a Combinatorial Triangulation

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月21日

查看全文
  • Belén Cruces,
  • Clemens Huemer,
  • Dolores Lara

摘要

In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and n additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation T and a point set S such that T can be drawn on S in at least \(\varOmega (1,31^n)\) Ω ( 1 , 31 n ) ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.