The algorithm of Tutte for constructing convex planar straight-line drawings and the algorithm of Floater and Gotsman for constructing planar straight-line morphs are among the most popular graph drawing algorithms. Quite surprisingly, little is known about the resolution of the drawings produced by these algorithms. In this paper, focusing on maximal plane graphs, we prove tight bounds on the resolution of the planar straight-line drawings produced by Floater's algorithm, which is a broad generalization of Tutte's algorithm. Further, we use such a result in order to prove a lower bound on the resolution of the drawings of maximal plane graphs produced by Floater and Gotsman's morphing algorithm. Finally, we show that such a morphing algorithm might produce drawings with exponentially-small resolution, even when transforming drawings with polynomial resolution.
翻译：Tutte 的算法, 用于建造固定平面平面直线绘图的算法, 以及Floater 和 Gotsman 的算法, 用于建造平面直线形的算法, 是最受欢迎的图形绘图算法之一。 非常令人惊讶的是, 这些算法产生的图的解析度鲜为人知。 在这份以最大平面图为焦点的论文中, 我们证明对Floater 和 Gotsman 生成的平面图解析的解析线直线图的解算法有着紧密的解析线。 此外, 我们使用这样的算法, 证明对由 Floater 和 Gotsman 生成的最大平面图的解析法的解析度的解析度较低。 最后, 我们显示, 这样的变形算法可能会产生具有指数小分辨率的图, 即使用多元分辨率转换图。
相关内容
微信扫码咨询专知VIP会员