Counting Plane Graphs: CrossGraph Charging SchemesSharir, Micha and Sheffer, Adam (2013) Counting Plane Graphs: CrossGraph Charging Schemes. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 1930(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractWe study crossgraph charging schemes for graphs drawn in the plane. These are charging schemes where charge is moved across vertices of different graphs. Such methods have been recently applied to obtain various properties of triangulations that are embedded over a fixed set of points in the plane. We show how this method can be generalized to obtain results for various other types of graphs that are embedded in the plane. Specifically, we obtain a new bound of $O^*\left(187.53^N \right)$ for the maximum number of crossingfree straightedge graphs that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound 207.85^N in Hoffmann et al.[14]). We also derive upper bounds for numbers of several other types of plane graphs (such as connected and biconnected plane graphs), and obtain various bounds on expected vertexdegrees in graphs that are uniformly chosen from the set of all crossingfree straightedge graphs that can be embedded over a specific point set. We then show how to apply the crossgraph chargingscheme method for graphs that allow certain types of crossings. Specifically, we consider graphs with no set of k pairwisecrossing edges (more commonly known as kquasiplanar 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 straightedge kquasiplanar embedding over S is only exponential in N.
Actions (login required)
