Drawing plane triangulations with few segments

摘要

Dujmovie et al. (2007) [6] showed that every 3-connected plane graph G with n vertices admits a straight-line drawing with at most 2.5n - 3 segments, which is also the best known upper bound when restricted to plane triangulations. On the other hand, they showed that there exist triangulations requiring 2n - 6 segments. In this paper we show that every plane triangulation admits a straight-line drawing with at most (7n - 2 Delta(0) - 10)/3 = 2.33n segments, where Delta(0) is the number of cyclic faces in the minimum realizer of G. For general plane graphs with n vertices and m edges, our algorithm requires at most (16n - 3m - 28)/3 = 5.33n - m segments, which is less than 2.5n - 3 for all m = 2.84n. In the context of grid drawings, where the vertices are restricted to have integer coordinates, we show that every triangulation with maximum degree D can be drawn with at most 2n + t - 3 segments and 0 (8(t) . D-2t) area, where t is the minimum number of leaves over all the trees of the minimum realizer. This is the first nontrivial attempt to simultaneously optimize the area and the number of segments while drawing triangulations. These results extend to the case when the goal is to optimize the number of slopes in the drawing. (C) 2018 Elsevier B.V. All rights reserved.