On the Number of Plane Graphs

被引：9

作者：

Aichholzer, Oswin ^{[1
]}

Hackl, Thomas ^{[1
]}

Vogtenhuber, Birgit ^{[1
]}

Huemer, Clemens ^{[2
]}

Hurtado, Ferran ^{[2
]}

Krasser, Hannes ^{[1
]}

机构：

[1] Graz Univ Technol, Inst Softwaretechnol, A-8010 Graz, Austria

[2] Univ Politecn Cataluna, Barcelona, Spain

来源：

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2006年

关键词：

D O I：

10.1145/1109557.1109613

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 graphs and connected plane graphs as well as the number of cycle-free plane 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 simple proofs that the number of spanning trees, cycle-free graphs (forests), perfect matchings, and spanning paths is also minimized for point sets in convex position. In addition we construct a new extremal configuration, the so-called double zig-zag, chain. Most noteworthy this example bears Theta*(root 72(n)) = Theta*(8.4853(n)) triangulations and 0*(41.1889(n)) plane graphs (omitting polynomial factors in both cases), improving the previously known best maximizing examples.

引用

页码：504 / +

页数：2

共 21 条

[1] Convexity minimizes pseudo-triangulations
Aichholzer, O
Aurenhammer, F
Krasser, H
Speckmann, B
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 28 (01): : 3 - 10
[2] A lower bound on the number of triangulations of planar point sets
Aichholzer, O
Hurtado, F
Noy, M
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 29 (02): : 135 - 145
[3] Enumerating order types for small point sets with applications
Aichholzer, O
Aurenhammer, F
Krasser, H
[J]. ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2002, 19 (03): : 265 - 281
[4] AICHHOLZER O, 2001, P 13 CAN C COMP GEOM, P17
[5] Aichholzer O., On the rectilinear crossing number
[6] AICHHOLZER O, 2004, P 20 EUR WORKSH COMP, P119
[7] AICHHOLZER O, 2002, P 18 ANN ACM S COMP, P19
[8] Aichholzer Oswin, 2005, P 21 S COMP GEOM, P91
[9] [Anonymous], 1982, Annals of Discrete Mathematics
[10] [Anonymous], P 13 CAN C COMP GEOM

← 1 2 3 →