Drawings of planar graphs with few slopes and segments
Drawings of planar graphs with few slopes and segments
复制标题
具有少量斜率和线段的平面图
DOI：
10.1016/j.comgeo.2006.09.002
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
V. Dujmović;D. Eppstein;M. Suderman;D. Wood
我们研究具有很少线段和很少斜率的平面图的直线图。所有树木均获得最佳结果。外平面图、2 树和平面 3 树获得紧界。我们证明，每个 n 个顶点上的 3 连通平面图都有最多 52n 个线段和最多 2n 个斜率的平面图。我们证明每个三次三连通平面图都有一个具有三个斜率（以及外表面上的三个弯曲）的平面图。在配套论文中，还考虑了具有很少斜率的非平面图的绘图。
We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 52n segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.