Counting Plane Graphs: Cross-Graph Charging Schemes

Source abstract

We study cross-graph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have recently been used to obtain various properties of triangulations that are embedded in a fixed set of points in the plane. We generalize this method to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of O *(187.53 N ) (where the O *(⋅) notation hides polynomial factors) for the maximum number of crossing-free straight-edge graphs that can be embedded in any specific set of N points in the plane (improving upon the previous best upper bound 207.85 N in Hoffmann, Schulz, Sharir, Sheffer, Tóth and Welzl [14]). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and bi-connected plane graphs), and obtain various bounds on the expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded in a specific point set. We then apply the cross-graph charging-scheme method to graphs that allow certain types of crossings. Specifically, we consider graphs with no set of k pairwise crossing edges (more commonly known as k -quasi-planar graphs). For k =3 and k =4, we prove that, for any set S of N points in the plane, the number of graphs that have a straight-edge k -quasi-planar embedding over S is only exponential in N .