Counting carambolas

DOI10.1007/S00373-015-1621-7MaRDI QIDQ293619zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Maarten Löffler, André Schulz, Csaba D. Tóth

Publication date 9 June 2016

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

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

zbMATH Keywords

triangulationconvex polygoncountingplane graphmonotone pathstar-shaped polygon

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Polytopes and polyhedra (52B99)

Abstract: We give upper and lower bounds on the maximum and minimum number of geometric configurations of various kinds present (as subgraphs) in a triangulation of $n$ points in the plane. Configurations of interest include emph{convex polygons}, emph{star-shaped polygons} and emph{monotone paths}. We also consider related problems for emph{directed} planar straight-line graphs.

Recommendations

• On the number of plane geometric graphs
• Convex polygons in geometric triangulations
• Convex Polygons in Geometric Triangulations
• Counting triangulations of planar point sets

Cites work

• Bounds on the maximum multiplicity of some common geometric graphs
• Computational geometry. Algorithms and applications.
• Convex polygons in geometric triangulations
• Counting carambolas
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Crossing-Free Subgraphs
• Flipping edges in triangulations
• How many potatoes are in a mesh?
• Matrix Analysis
• Monotone paths in planar convex subdivisions and polytopes
• On the Number of Cycles in Planar Graphs
• On the number of plane geometric graphs
• On the number of spanning trees a planar graph can have

Cited in

(5)

• Counting carambolas
• Convex Polygons in Geometric Triangulations
• Convex polygons in geometric triangulations
• On the number of plane geometric graphs
• Bimonotone subdivisions of point configurations in the plane

This page was built for publication: Counting carambolas

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