Lower bounds on the number of crossing-free subgraphs of KN

被引：58

作者：

García, A

Noy, M ^{[1
]}

Tejel, J

机构：

[1] Univ Politecn Catalunya, Dept Matemat Aplicada 2, E-08028 Barcelona, Spain

[2] Univ Zaragoza, Fac Ciencias, Dept Metodos Estadist, E-50009 Zaragoza, Spain

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2000年 / 16卷 / 04期

关键词：

D O I：

10.1016/S0925-7721(00)00010-9

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We improve previous lower bounds on the number of simple polygonizations, and other kinds of crossing-free subgraphs, of a set of N points in the plane by analyzing a suitable configuration. We also prove that the number of crossing-free perfect matchings and spanning trees is minimum when the points are in convex position. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：211 / 221

页数：11

共 17 条

[1]

Akl S., 1979, ARS COMBINATORIA, V7, P7

[2]

[Anonymous], 1982, Annals of Discrete Mathematics

[3] ASYMPTOTIC METHODS IN ENUMERATION [J].