不同美學準則之最佳化二維圖形繪製演算法

隨著圖形在不同科學與工程領域中被獲知是最重要的抽象化結構之一，圖形繪製已冒出成為計算機科學中一個快速成長的研究主題。傳統的圖形繪製演算法被設計來遵循好的繪圖之一個或多個美學準則。本研究探討從最簡單到最複雜的三種圖形種類之二維繪圖上不同美學準則之最佳化。首先、我們研究有根樹之氣球繪圖。在此種繪圖中，每一個子樹被繪製成包在一個圓形當中，而且角度的大小會嚴重地影響繪圖的清晰度。因此，本研究探討在不同氣球繪圖設定下不同角度測度之最佳化問題，其中包含了最佳化之角解析度、最大角與最小角之比率、和角度之標準差。另外，本研究還提供了在氣球繪圖上的幾個應用。其次、我們研究雙層與三層網路繪圖(其中每一個結點分別被畫在兩條和三條垂直線上)及其應用在多對一邊界標示。在多對一邊界標示中，地圖上所有的標籤被置放在包圍著所有特徵點之矩形地圖的四邊上，其中一個以上的特徵點允許連接到共同的標籤，特徵點與標籤之間是用指線(可能是縱橫線段或直線段)所連接。本研究利用雙層與三層網路繪圖來解決在一些單邊與雙邊標示機制下之指線交叉數目最少化問題。更進一步地，我們用超指線換掉指線並採用傀儡標籤來設計完全沒有交叉的邊界標示法。再次、我們研究平面圖之能見表示法。在此表示法中，每一個結點被畫成水平線段，使得對應到兩相連結點之兩條水平線段在垂直方向上彼此能見。給定一個n個結點之平面圖，本研究設計一個O(n)時間之演算法，來找出寬度不超過之此平面圖之能見表示法。我們的結果在寬度上界達到最佳化，因為我們的寬度上界與過去已知最佳之寬度下界只差一單位。

關鍵字

圖形繪製；圖形演算法；氣球繪圖；邊界標示；能見表示法

並列摘要

As graphs are known to be one of the most important abstract models in various scientific and engineering areas, graph drawing has naturally emerged as a fast growing research topic in computer science. Conventional graph drawing algorithms are designed to confirm to one or more aesthetic criteria of nice drawings. In this research, we investigate to optimize various aesthetic criteria in two-dimensional drawings of three graph classes, form the simplest to the most complicated. First, we study balloon drawings of rooted trees, in which each subtree is enclosed in a circle. In balloon drawings, the sizes of the drawing angles significantly affect the drawing articulation. Therefore, in this research, we investigate the problem of optimizing various measures of angles, i.e., angular resolution, aspect ratio of angles, as well as standard deviation of angles, under different setting of balloon drawings. In addition, we provide some applications on balloon drawings. Second, we study two- and three- layered network drawings (in which nodes are drawn on two and three vertical lines, respectively) with application to many-to-one boundary labeling, in which more than one point site allows to be connected to a common label on the four sides of an enclosing rectangular map by a leader (which may be a rectilinear or straight line segment). In this research, we apply two- and three- layered network drawings to solving the problem of minimizing the number of crossings among leaders under certain one-side and two-side labeling schemes. Furthermore, we design the labeling without any crossing by substituting hyperleaders for leaders and applying dummy labels. Third, we study the visibility representations of plane graphs, in which each node is drawn as a horizontal line segment such that the line segments associated with any two adjacent nodes are vertically visible to each other. In this research, we give an O(n)-time algorithm to find a visibility representation of an n-node plane graph no wider than $ /lfloor 4n/3 /rfloor - 2 $, which achieves optimality in the upper bound of width because the bound differs from the previously known lower bound only by one unit.

並列關鍵字

graph drawing ； graph algorithm ； balloon drawing ； boundary labeling ； visibility representation

參考文獻

[1] J. Barnes and P. Hut. A hierarchical O(N log N) force-cacluation algorithm. Nature, 324:446–451, 1986.

[2] M. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Boundary labelling of optimal total leader length. In Proc. of PCI 2005, volume 3746 of Lecture Notes in Computer Science, pages 80–89. Springer, 2005.

[4] M. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: models and efficient algorithms for rectangular maps. In Proc. of GD 2004, volume 3383 of Lecture Notes in Computer Science, pages 49–59. Springer, 2004.

[5] M. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: models and efficient algorithms for rectangular maps. Computational Geometry: Theory and Applications, 36(3):215–236, 2006.

[6] M. Bekos and A. Symvonis. BLer: a boundary labeller for technical drawings. In Proc. of GD 2005, volume 3843 of Lecture Notes in Computer Science, pages 503–504. Springer, 2006.

國際替代計量

不同美學準則之最佳化二維圖形繪製演算法

全文下載

主題瀏覽