Planar drawings of graphs tend to be favored over non-planar drawings. Testing planarity and creating a planar layout of a planar graph can be done in linear time. However, creating readable drawings of nearly planar graphs remains a challenge. We therefore seek to answer which edges of nearly planar graphs create clutter in their drawings generated by mainstream graph drawing algorithms. We present a heuristic to identify problematic edges in nearly planar graphs and adjust their weights in order to produce higher quality layouts with spring-based drawing algorithms. Our experiments show that our heuristic produces significantly higher quality drawings for augmented grid graphs, augmented triangulations, and deep triangulations.
翻译:平面图的绘制通常比非平面图更受青睐。测试平面性并创建平面图布局可以在线性时间内完成。然而,在近平面图的可读性绘制中仍存在挑战。因此,我们试图回答哪些近平面图的边在由主流图形绘制算法生成的绘图中会产生混乱。我们提出了一种启发式方法来识别近平面图中的有问题的边,并调整它们的权重,以使用基于弹簧的绘图算法生成更高质量的布局。我们的实验表明,对于增强网格图、增强三角剖分和深度三角剖分,我们的启发式方法可以生成显着更高质量的绘图。