Counting plane graphs: cross-graph charging schemes

DOI10.1017/S096354831300031XMaRDI QIDQ5397740zbMATH OpenOpenAlexFDO

Authors Adam Sheffer, Micha Sharir

Publication date 24 February 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.0194

zbMATH Keywords

bi-connected plane graphsconnected plane graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62)

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 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^{\ast }(187.53^N)$ (where the $O^{\ast }()$ notation hides polynomial factors) for the maximum number of crossing-free straight-edge 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.). 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 expected vertex-degrees in graphs that are uniformly chosen from the set of all crossing-free straight-edge graphs that can be embedded over a specific point set. We then show how to apply the cross-graph charging-scheme method for 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$.

Recommendations

• Counting Plane Graphs: Cross-Graph Charging Schemes
• Counting triangulations of planar point sets
• Quasi-planar graphs have a linear number of edges

Cites work

• A better upper bound on the number of triangulations of a planar point set
• Analytic combinatorics of non-crossing configurations
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Number of crossing-free geometric graphs vs. Triangulations
• On degrees in random triangulations of point sets
• On the maximum number of edges in quasi-planar graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On the number of plane geometric graphs
• Surveys on Discrete and Computational Geometry
• Thirty Essays on Geometric Graph Theory

Cited in

(12)

• A new lower bound on the maximum number of plane graphs using production matrices
• The Mathematics of Ferran Hurtado: A Brief Survey
• On the number of anchored rectangle packings for a planar point set
• On the number of anchored rectangle packings for a planar point set
• Convex polygons in geometric triangulations
• Crossings in grid drawings
• A census of plane graphs with polyline edges
• Counting Plane Graphs: Cross-Graph Charging Schemes
• A Census of Plane Graphs with Polyline Edges
• Convex Polygons in Geometric Triangulations
• An upper bound for the number of rectangulations of a planar point set
• Non-crossing Hamiltonian paths and cycles in output-polynomial time

This page was built for publication: Counting plane graphs: cross-graph charging schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5397740)