Counting Carambolas
arXiv:1410.1579 · doi:10.1007/s00373-015-1621-7
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 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.
update reflects journal version, to appear in Graphs and Combinatorics; 18 pages, 13 figures