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 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		[HPS18]		[SS12]
Triangulations		[RW22]		[SS11]
Spanning Cycles		[GNT00]		[SSW13]
Perfect Matchings		[AR15]		[SW06]
Spanning Trees		[HM13]		[HSSTW11; SS11]
Cycle-Free Graphs		[HM13]		[HSSTW11; SS11]

Some less common variants:

Graph Type	Lower Bound	Reference	Upper Bound	Reference
Connected Graphs		[AHHHKV]		[SS12]
Pseudo Triangulations		[AOSS08]		[BSS13; SS11]
Pointed Pseudo Triangulations		[AOSS08]		[BSS13; SS11]
All Matchings		[SW06]		[SW06]
Left-Right Perfect Matchings		[SW06]		[SW06]
Red-Blue Perfect Matchings		[SW06]		[SW06]
Rectangulations		[Fels13]		[AP22]
Quadrangulations		[ScS11]		[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 , 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.