On the number of plane geometric graphs

DOI10.1007/s00373-007-0704-5zbMath1119.05056OpenAlexW2000008376WikidataQ61732493 ScholiaQ61732493MaRDI QIDQ2373434

Birgit Vogtenhuber, Hannes Krasser, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Oswin Aichholzer

Publication date: 19 July 2007

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-007-0704-5

zbMATH Keywords

acyclic graphsdouble zig-zag chain

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (31)

Configurations of non-crossing rays and related problems ⋮ Counting carambolas ⋮ Convex Polygons in Geometric Triangulations ⋮ Convex Polygons in Geometric Triangulations ⋮ Order on order types ⋮ On the number of crossing-free partitions ⋮ Perfect matchings with crossings ⋮ An upper bound for the number of rectangulations of a planar point set ⋮ The Mathematics of Ferran Hurtado: A Brief Survey ⋮ Point sets with many non-crossing perfect matchings ⋮ Colored ray configurations ⋮ On numbers of pseudo-triangulations ⋮ From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices ⋮ Counting Plane Graphs: Cross-Graph Charging Schemes ⋮ Counting polygon triangulations is hard ⋮ Counting Plane Graphs with Exponential Speed-Up ⋮ Fast enumeration algorithms for non-crossing geometric graphs ⋮ Flips in planar graphs ⋮ Counting triangulations of some classes of subdivided convex polygons ⋮ Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees ⋮ Perfect matchings with crossings ⋮ Unnamed Item ⋮ Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees ⋮ Transition operations over plane trees ⋮ Twenty years of progress of \(\mathrm{JCDCG}^3\) ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees ⋮ A new lower bound on the maximum number of plane graphs using production matrices ⋮ A Census of Plane Graphs with Polyline Edges ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Counting triangulations and other crossing-free structures via onion layers

Cites Work

• Unnamed Item
• Unnamed Item
• Convexity minimizes pseudo-triangulations
• On the crossing number of complete graphs
• Abstract order type extension and new results on the rectilinear crossing number
• Analytic combinatorics of non-crossing configurations
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• The polytope of non-crossing graphs on a planar point set
• Enumerating order types for small point sets with applications
• A better upper bound on the number of triangulations of a planar point set
• A lower bound on the number of triangulations of planar point sets
• On the number of pseudo-triangulations of certain point sets
• Research Problems in Discrete Geometry
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• On the number of plane graphs
• On the number of crossing-free matchings, (cycles, and partitions)
• Crossing-Free Subgraphs

This page was built for publication: On the number of plane geometric graphs