Hexagonal Grid Drawings: Algorithms and Lower Bounds
Hexagonal Grid Drawings: Algorithms and Lower Bounds
复制标题
六角网格图：算法和下界
DOI：
10.1007/978-3-540-31843-9_3
复制
发表时间：
2004
影响因子：
2.7
通讯作者：
T. Biedl
中科院分区：
文献类型：
--
作者：
Shabnam Aziza;T. Biedl
我们研究六角形（三角形）网格上最大六度图的绘图，主要重点是保持较小的弯曲数量。我们给出的算法可以对所有简单图实现 3.5n+3.5 次弯曲。我们还证明了 K7 弯曲数量的最佳下界，并给出了不同连通性的图类的渐近下界。
We study drawings of graphs of maximum degree six on the hexagonal (triangular) grid, with the main focus of keeping the number of bends small. We give algorithms that achieve 3.5n+3.5 bends for all simple graphs. We also prove optimal lower bounds on the number of bends for K7, and give asymptotic lower bounds for graph classes of varying connectivity.