顏嗣鈞臺灣大學:電機工程學研究所林春成Lin, Chun-ChengChun-ChengLin2010-07-012018-07-062010-07-012018-07-062009U0001-3012200800453700http://ntur.lib.ntu.edu.tw//handle/246246/188017隨著圖形在不同科學與工程領域中被獲知是最重要的抽象化結構之一，圖形繪製已冒出成為計算機科學中一個快速成長的研究主題。傳統的圖形繪製演算法被設計來遵循好的繪圖之一個或多個美學準則。本研究探討從最簡單到最複雜的三種圖形種類之二維繪圖上不同美學準則之最佳化。先、我們研究有根樹之氣球繪圖。在此種繪圖中，每一個子樹被繪製成包在一個圓形當中，而且角度的大小會嚴重地影響繪圖的清晰度。因此，本研究探討在不同氣球繪圖設定下不同角度測度之最佳化問題，其中包含了最佳化之角解析度、最大角與最小角之比率、和角度之標準差。另外，本研究還提供了在氣球繪圖上的幾個應用。次、我們研究雙層與三層網路繪圖(其中每一個結點分別被畫在兩條和三條垂直線上)及其應用在多對一邊界標示。在多對一邊界標示中，地圖上所有的標籤被置放在包圍著所有特徵點之矩形地圖的四邊上，其中一個以上的特徵點允許連接到共同的標籤，特徵點與標籤之間是用指線(可能是縱橫線段或直線段)所連接。本研究利用雙層與三層網路繪圖來解決在一些單邊與雙邊標示機制下之指線交叉數目最少化問題。更進一步地，我們用超指線換掉指線並採用傀儡標籤來設計完全沒有交叉的邊界標示法。次、我們研究平面圖之能見表示法。在此表示法中，每一個結點被畫成水平線段，使得對應到兩相連結點之兩條水平線段在垂直方向上彼此能見。給定一個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.irst, 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.econd, 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.hird, 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.TABLE OF CONTENTS 頁次試委員會審定書 .................................................. i辭 .................................................. ii文摘要 .................................................. iiibstract .................................................. ivhapter 1: Introduction .................................................. 11.1 Balloon Drawing of Rooted Trees .................................................. 21.2 Two- and Three- Layered Network Drawings with Application to Many-to-One Boundary Labeling .................................................. 51.3 Visibility Representations of Plane Graphs .................................................. 131.4 Organization of this Research .................................................. 14hapter 2: Balloon Drawings of Rooted Trees .................................................. 152.1 Preliminaries .................................................. 152.2 Case C1 (Unordered Trees with Even Sub-Wedges) .................................................. 212.3 Case C2 (Ordered Trees with Flexible Uneven Sub-Wedges) .................................................. 252.4 Cases C3 and C4 (Unordered Trees with Fixed/Flexible Uneven Sub-Wedges) .................................................. 272.5 Applications .................................................. 40hapter 3: Two- and Three- Layered Network Drawings with Application to Many-to-One Boundary Labeling .................................................. 423.1 Preliminaries .................................................. 423.2 The Crossing Problem for One-Side Many-to-One Labeling with Type-opo Leaders .................................................. 463.3 The Crossing Problem for Two-Side Many-to-One Labeling with Type-opo Leaders .................................................. 523.4 The Crossing Problem for One-Side Many-to-One Labeling with Type-po Leaders .................................................. 623.5 The Crossing Problem for Two-Side Many-to-One Labeling with Type-po Leaders .................................................. 663.6 Discussions .................................................. 703.7 Many-to-One Boundary Labeling Using Hyperleaders and Dummy Labels .................................................. 71hapter 4: Visibility Representations of Plane Graphs .................................................. 784.1 Preliminaries .................................................. 784.2 Our Results .................................................. 81hapter 5: Conclusions and Future Work .................................................. 115eferences .................................................. 118ABLE OF FIGURESigure Number Page.1 Overview of this research .................................................. 2.2 Illustration of balloon drawings with (a) even sub-wedges and (b) uneven sub-wedges, where each node is drawn by a small red point; each edge is drawn by a solid straight line segment; the center of the largest circle in a balloon drawing is the root node .................................................. 3.3 The balloon drawings with even sub-wedges under two different tree orderings, where (b) achieves the optimality of RE1 and RA1 .................................................. 5.4 An example for labeling a server motherboard .................................................. 9.5 Other labeling approaches .................................................. 9.6 Illustration of leaders .................................................. 10.7 Illustration of boundary labeling with hyperleaders and dummy labels .................................................. 10.8 (a) A plane triangulation and (b) its visibility representation .................................................. 13.1 The SNS approach. (a) Node O is not the root, and the edge between O and its parent goes through a circle with radius R_{min}; (b) is a star graph centered at c_0 .................................................. 16.2 Notations used in a balloon drawing of a star graph with uneven sub-wedges .................................................. 16.3 An example for 2SAL and 2SLW .................................................. 20.4 An experimental result. (The above is its statistics.) .................................................. 25.5 An example showing how Algorithm 3 works .................................................. 33.6 An example showing how Algorithm 4 works. (a) Certain N_{S_i''} with |S_i''| = 15 in N_{APX}. (b) Illustration of the Δφ induced by (a) .................................................. 38.7 Applications to galaxy systems and H-graphs .................................................. 41.1 A four-side many-to-one labeling with type-s leaders .................................................. 44.2 An example reducing from DCP to DMCP .................................................. 48.3 The first category of crossings .................................................. 48.4 The second category of crossings .................................................. 48.5 (a) A instance of two-layered network. (b) The boundary labeling corresponding to (a) .................................................. 48.6 (a) All the possible cases where bends of two leaders are drawn in region T_1. (b) All the possible cases where the bend of leader p_a l_b (resp., p_c l_d) is drawn in region T_1 (resp., T_2)……………………………………………………. 48.7 The distribution of some animals in Taiwan, which is represented by one-side many-to-one labeling with type-opo leaders .................................................. 51.8 Two boundary labeling layouts with type-opo leaders for the same map .................................................. 52.9 G'' (L_0'', L_L'', L_R'', E'') with |L_0''| = N + n(2 C^N_2 + 2) and L_R'' = L1 .................................................. 55.10 The distribution of some animals in Taiwan, which is represented by two-side many-to-one labeling with type-opo leaders .................................................. 62.11 A special case of DCP1ML-po where the y-coordinate of any site is smaller than that of the lowest port of the lowest label. Note that some of the edges are not shown in the figure .................................................. 63.12 The experimental results for DCP1ML-po .................................................. 66.13 A special case of DCP2ML-po where the y-coordinate of any site is smaller than that of the lowest port among the ports of all labels. Note that some of the edges are not shown in the figure .................................................. 67.14 A crossing is produced when the x-coordinate increasing order of two sites does not respect the circular ordering of their corresponding labels, in the case where the two sites are connected to (a) the West side, (b) different sides, and (c) the East side .................................................. 68.15 An example for illustrating how Algorithm 10 is executed .................................................. 69.16 The experimental results for DCP2ML-po .................................................. 70.17 The outputs of an example for each step in Algorithm 12 .................................................. 75.1 Illustration of the coalescing and splitting operations .................................................. 80.2 Illustration of L-shapes .................................................. 82.3 Six possible visibility drawings for a good face v_p v_q v_r .................................................. 83.4 The β_1 operation of node v_{k+1} executed at a right L-shape .................................................. 83.5 The β_2 operation of node v_{k+1} executed at two adjacent L-shapes .................................................. 83.6 The β_3 operation of node v_{k+1} executed at three adjacent L-shapes .................................................. 84.7 Intermediate steps of an example for Algorithm 13 .................................................. 86.8 Discussion of three possible pairs of input L-shapes of a β_3 operation .................................................. 92.9 Illustration of the adjustment of the visibility embedding of faces b_1 and b_2 in case (1-ii-b) of Figure 4.6(a). In general, the y-coordinates of the bases of L-shapes of b_1 and b_2 may not be the same .................................................. 94.10 Illustration of a μ_i operation for i >= 1 .................................................. 96.11 An example of four consecutive μ_1 operations executed at a good face f. Note that the light grey drawings are adjusted to be good for the later μ_1 operation, whereas the dark grey drawings mean those that have been handled .................................................. 100.12 Illustration of subcase (a1) .................................................. 104.13 Illustration of subcase (a2) .................................................. 104.14 Illustration of a μ1 operation executed at face f_1, which is produced after executing a μ3 operation .................................................. 108.15 An example of the comparison between the μ1 operations respectively executed at face f_{k,1} in D(H_k) and face f_1 in D(H_{k+1}) .................................................. 110.16 Illustration of how to adjust face f_1 to be good, when w_b(D_2(f_{k,1})) = 2 .................................................. 110.17 Illustration of how to adjust face f_1 to be good, when w_b(D_2(f_{k,1})) = 1 .................................................. 110.18 First μ_2 and then μ_1 operations can be viewed as first μ1 and then μ_3 operations .................................................. 111.19 Three possible cases of the drawing after executing a u_2 operation at a U-shape .................................................. 113IST OF TABLESigure Number Page.1 The time complexity for optimizing main aesthetic criteria of balloon drawing .................................................. 6.2 The time complexity of the problems for the boundary labeling subject to the constraints where the locations of ports of each labels are fixed; the labels along the same side are of uniform (maximum) size .................................................. 11.1 The three pairs of the input L-shapes of the β_1, β_2, and β_3 operations .................................................. 911913104 bytesapplication/pdfen-US圖形繪製圖形演算法氣球繪圖邊界標示能見表示法graph drawinggraph algorithmballoon drawingboundary labelingvisibility representationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/188017/1/ntu-98-F89921122-1.pdf