A new lower bound on the maximum number of plane graphs using production matrices

DOI10.1016/J.COMGEO.2019.07.005MaRDI QIDQ2331222zbMATH OpenOpenAlexFDO

Authors Clemens Huemer, Alexander Pilz, Rodrigo I. Silveira

Publication date 25 October 2019

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

graphs countinglower boundsplane graphsproduction matrix

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We use the concept of production matrices to show that there exist sets of $n$ points in the plane that admit $Omega(42.11^n)$ crossing-free geometric graphs. This improves the previously best known bound of $Omega(41.18^n)$ by Aichholzer et al. (2007).

Recommendations

• New results on production matrices for geometric graphs
• Production matrices for geometric graphs
• New production matrices for geometric graphs
• On the number of plane geometric graphs
• Number of crossing-free geometric graphs vs. Triangulations

Cites work

• A lower bound on the number of triangulations of planar point sets
• An improved lower bound on the minimum number of triangulations
• Analytic combinatorics of non-crossing configurations
• Bounds on the maximum multiplicity of some common geometric graphs
• Characteristic polynomials of production matrices for geometric graphs
• Convexity minimizes pseudo-triangulations
• Counting plane graphs: cross-graph charging schemes
• Crossing-Free Subgraphs
• ECO:a methodology for the enumeration of combinatorial objects
• Generating trees and proper Riordan arrays
• Geometric tree graphs of points in convex position
• Graph of triangulations of a convex polygon and tree of triangulations
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 1409186 (Why is no real title available?)
• Lower bounds on the maximum number of non-crossing acyclic graphs
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On the number of plane geometric graphs
• On the number of plane graphs
• Point sets with many non-crossing perfect matchings
• Probability and Computing
• Production matrices
• Production matrices for geometric graphs
• The on-line encyclopedia of integer sequences

Cited in

(7)

• Characteristic polynomials of production matrices for geometric graphs
• New results on production matrices for geometric graphs
• Enumeration of bipartite non-crossing geometric graphs
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices
• New production matrices for geometric graphs
• Production matrices for geometric graphs
• On fully diverse sets of geometric objects and graphs

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: A new lower bound on the maximum number of plane graphs using production matrices

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