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]
\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]


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.
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.
Hannah Ashbach and Kiki Pichini, An Upper Bound for the Number of Rectangulations of a Planar Point Set, arXiv:1911.09740.
Andrei Asinowski and Günter Rote, Point sets with many non-crossing matchings, arXiv:1502.04925.
Moria Ben-Ner, André Schulz, and Adam Sheffer, On Numbers of Pseudo-Triangulations, Comput. Geom. Theory Appl., 46 (2013), 688–699.
Stefan Felsner, Exploiting Air-Pressure to Map Floorplans on Point Sets, Proc. Graph Drawing 2013, Springer International Publishing, 196–207.
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.
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.
Clemens Huemer and Anna de Mier, Lower bounds on the maximum number of non-crossing acyclic graphs, arXiv:1310.5882.
Clemens Huemer, Alexander Pilz, and Rodrigo I. Silveira, A New Lower Bound on the Maximum Number of Plane Graphs using Production Matrices.
André Schulz and Adam Sheffer, Improved Analysis of Recent Techniques for Counting Plane Graphs, Unpublished manuscript. Contact me for more details.
Micha Sharir and Adam Sheffer, Counting triangulations
of planar point sets
, Electr. J. Comb., 18(1) (2011).
Micha Sharir and Adam Sheffer, Counting Plane Graphs: Cross-Graph Charging Schemes, Combinat. Probab. Comput., 22 (2013), 935–954.
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.
Micha Sharir and Emo Welzl, On the number of crossing-free matchings, cycles, and partitions, SIAM J. Comput. 36 (2006), 695-720.
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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s