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(41.18^N)  [AHHHKV] O(187.53^N)  [SS12]
Triangulations \Omega(8.65^N)  [DSST11] 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(18^N)  [Ack06]
Quadrangulations \Omega(4^N)  [ScS11] O(51.06^N)  [ScS11]

References

[Ack06]
Eyal Ackerman, Counting Problems for Geometric Structures: Rectangulations, Floorplans, and Quasi-Planar Graphs, Ph.D. thesis, Technion-Israel Institute of Technology, 2006.
[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.
[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.
[DSST11]
Adrian Dumitrescu, André Schulz, Adam Sheffer, and Csaba D. Tóth, Bounds on the maximum multiplicity of some common geometric graphs, Proc. 28th International Symposium on Theoretical Aspects of Computer Science (2011), 637–648.
[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.
[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 WelzlCounting 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.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s