Counting Plane Graphs: Cross-Graph Charging Schemes

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