Experimental Evaluation of Book Drawing Algorithms
Experimental Evaluation of Book Drawing Algorithms
复制标题
书籍绘图算法的实验评估
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Nöllenburg
中科院分区：
文献类型：
--
作者：
J. Klawitter;T. Mchedlidze;M. Nöllenburg
一个图（G=（V，E））的k页书图由它的顶点沿着一个脊沿着的线性排序和每个边到k页之一的分配组成，k页是由脊限定的半平面。在书籍绘图中，当且仅当两条边指定给同一页且它们的顶点沿书脊沿着交替时，这两条边才相交。k页书籍绘图中的交叉最小化是NP难的，但书籍绘图在可视化和其他方面有多种应用。因此，存在几种启发式书籍绘制算法，但没有更广泛的比较研究，他们的相对性能。在本文中，我们提出了一个全面的基准集具有挑战性的图形类的书籍绘制算法，并提供了一个广泛的实验研究现有的书籍绘制算法的性能。
A k-page book drawing of a graph (G=(V,E)) consists of a linear ordering of its vertices along a spine and an assignment of each edge to one of the k pages, which are half-planes bounded by the spine. In a book drawing, two edges cross if and only if they are assigned to the same page and their vertices alternate along the spine. Crossing minimization in a k-page book drawing is NP-hard, yet book drawings have multiple applications in visualization and beyond. Therefore several heuristic book drawing algorithms exist, but there is no broader comparative study on their relative performance. In this paper, we propose a comprehensive benchmark set of challenging graph classes for book drawing algorithms and provide an extensive experimental study of the performance of existing book drawing algorithms.