科研之友
微信
新浪微博
Facebook
分享链接
摘要
We study vertex-labeled graphs that can be embedded on a given point set such that every edge is a polyline with k bends per edge, where k is an element of N. It is shown that on every n -element point set in the plane, at most exp(O (n log(2 + k))) labeled graphs can be embedded using polyline edges with k bends per edge, and this bound is the best possible. This is the fi rst exponential upper bound for the number of labeled plane graphs where the edges are polylines of constant complexity. Standard tools developed for the enumeration of straight-line graphs, such as triangulations and crossing numbers, do not seem applicable 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 labeled planar graphs that admit an embedding with x -monotone edges on n points is superexponential.
- 出版日期2017
