Archambault Daniel, Munzner Tamara, Auber David
University of British Columbia.
IEEE Trans Vis Comput Graph. 2006 Sep-Oct;12(5):813-20. doi: 10.1109/TVCG.2006.177.
Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component. That tree is drawn with a new area-aware variant of a tree drawing algorithm that handles high-degree nodes gracefully, at the cost of allowing edge-node overlaps. SPF performs an order of magnitude faster than the best previous approaches, while producing drawings of commensurate or improved quality.
准树，即具有树状结构的图，出现在许多应用领域，包括生物信息学和计算机网络。我们新的SPF方法采用两级绘制方法利用这些图的结构，其中图被分解为双连通分量树。低级双连通分量采用力导向方法绘制，该方法使用生成树骨架作为布局的起点。图的高级结构是一棵真正的树，其具有可变大小的元节点，每个元节点包含一个双连通分量。该树使用一种新的区域感知变体树绘制算法绘制，该算法能很好地处理高度数节点，代价是允许边与节点重叠。SPF的执行速度比之前最好的方法快一个数量级，同时生成质量相当或更高的图。
