# Numbers of Plane Graphs Six points in a convex position have 14 triangulations.
What is the maximal number of graphs of type X that can be embedded over a specific set of $N$ points in the plane? The purpose of this webpage is to present up-to-date bounds for various types of plane graphs. We only consider straight-edge crossing-free graphs. For a more detailed explanation about what these bounds are click here. Comments and updates are more than welcome.
We first consider the more popular variants – those with new works studying them every several years.
Graph Type Lower Bound Reference Upper Bound Reference
Plane Graphs $\Omega(42.11^N)$ [HPS18] $O(187.53^N)$ [SS12]
Triangulations $\Omega(9.08^N)$ [RW22] $30^N$ [SS11]
Spanning Cycles $\Omega(4.64^N)$ [GNT00] $O(54.55^N)$ [SSW13]
Perfect Matchings $\Omega(3.09^N)$ [AR15] $O(10.05^N)$ [SW06]
Spanning Trees $\Omega(12.52^N)$ [HM13] $O(141.07^N)$ [HSSTW11; SS11]
Cycle-Free Graphs $\Omega(13.61^N)$ [HM13] $O(160.55^N)$ [HSSTW11; SS11]
Some less common variants:
Graph Type Lower Bound Reference Upper Bound Reference
Connected Graphs $\Omega(35.49^N)$ [AHHHKV] $O(186.46^N)$ [SS12]
Pseudo
Triangulations $\Omega(20^N)$ [AOSS08] $120^N$ [BSS13; SS11]
Pointed Pseudo Triangulations $\Omega(12^N)$ [AOSS08] $O(89.1^N)$ [BSS13; SS11]
All Matchings $\Omega(4^N)$ [SW06] $O(10.43^N)$ [SW06]
Left-Right Perfect Matchings $\Omega(2^N)$ [SW06] $O(5.38^N)$ [SW06]
Red-Blue Perfect Matchings $\Omega(2^N)$ [SW06] $O(7.61^N)$ [SW06]
Rectangulations $\Omega(8^N)$ [Fels13] $O(16.84^N)$ [AP22]
Quadrangulations $\Omega(4^N)$ [ScS11] $O(51.06^N)$ [ScS11]

## References

[AHHHKV]
Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber, On the number of plane geometric graphs, Graphs and Combinatorics, 23(1) (2007), 67-84.
[AOSS08]
Oswin Aichholzer, David Orden, Francisco Santos, and Bettina Speckmann, On the number of pseudo-triangulations of certain point sets, Journal of Combinatorial Theory, Series A 115(2) (2008), 254-278.
[AP22]
Hannah Ashbach and Kiki Pichini, An Upper Bound for the Number of Rectangulations of a Planar Point Set, arXiv:1911.09740.
[AR15]
Andrei Asinowski and Günter Rote, Point sets with many non-crossing matchings, arXiv:1502.04925.
[BSS13]
Moria Ben-Ner, André Schulz, and Adam Sheffer, On Numbers of Pseudo-Triangulations, Comput. Geom. Theory Appl., 46 (2013), 688–699.
[Fels13]
Stefan Felsner, Exploiting Air-Pressure to Map Floorplans on Point Sets, Proc. Graph Drawing 2013, Springer International Publishing, 196–207.
[GNT00]
Alfredo García, Marc Noy, and Javier Tejel, Lower bounds on the number of crossing-free subgraphs of $K_N$, Computational Geometry: Theory and Applications, 16 (2000), 211–221.
[HSSTW11]
Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl, Counting Plane Graphs: Flippability and its Applications, Proc. 12th Symp. on Algs. and Data structs, (2011), 524–535.
[HM13]
Clemens Huemer and Anna de Mier, Lower bounds on the maximum number of non-crossing acyclic graphs, arXiv:1310.5882.
[HPS18]
Clemens Huemer, Alexander Pilz, and Rodrigo I. Silveira, A New Lower Bound on the Maximum Number of Plane Graphs using Production Matrices.
[ScS11]
André Schulz and Adam Sheffer, Improved Analysis of Recent Techniques for Counting Plane Graphs, Unpublished manuscript. Contact me for more details.
[SS11]
Micha Sharir and Adam Sheffer, Counting triangulations
of planar point sets
, Electr. J. Comb., 18(1) (2011).
[SS12]
Micha Sharir and Adam Sheffer, Counting Plane Graphs: Cross-Graph Charging Schemes, Combinat. Probab. Comput., 22 (2013), 935–954.
[SSW13]
Micha Sharir, Adam Sheffer, and Emo Welzl, Counting Plane Graphs: Perfect Matchings, Spanning Cycles, and Kasteleyn’s Technique, J. Combinat. Theory A, 120 (2013), 777–794.
[SW06]
Micha Sharir and Emo Welzl, On the number of crossing-free matchings, cycles, and partitions, SIAM J. Comput. 36 (2006), 695-720.
[RW22]
Daniel Rutschmann and Manuel Wettstein, Chains, Koch Chains, and Point Sets with many Triangulations, Proc. 38th International Symposium on Computational Geometry (SoCG 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.