A Census of Plane Graphs with Polyline Edges
Andrea Francke, Csaba D. Tóth · 2014
It is shown that on every n-element point set in the plane, at most exp(O(kn)) labeled planar graphs can be embedded using polyline edges with k bends per edge. This is the first exponential upper bound for the number of labeled plane graphs where the edges are polylines of constant size. Several standard tools developed for the enumeration of straight-line graphs, such as triangulations and crossing numbers, are unavailable in this scenario. Furthermore, the exponential upper bound does not carry over to other popular relaxations of straight-line edges: for example, the number of plane graphs realizable with x-monotone edges on n points is already super-exponential.