請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41878完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞 | |
| dc.contributor.author | Chun-Cheng Lin | en |
| dc.contributor.author | 林春成 | zh_TW |
| dc.date.accessioned | 2021-06-15T00:35:32Z | - |
| dc.date.available | 2011-01-06 | |
| dc.date.copyright | 2009-01-06 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2008-12-30 | |
| dc.identifier.citation | [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. [3] M. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Polygons labelling of minimum leader length. In Proc. of APVIS 2006, volume 60 of Conferences in Research and Practice in Information Technology, pages 15–21. Australian Computer Society, 2006. [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. [7] M. Benkert, H. Haverkort, M. Kroll, and M. Nollenburg. Algorithms for multicriteria one-sided boundary labeling. In Proc. of GD 2007, volume 4875 of Lecture Notes in Computer Science, pages 243–254. Springer, 2008. [8] J. Carriere and R. Kazman. Research report: interacting with huge hierarchies: beyond cone trees. In Proc. of IV 1995, pages 74–81. IEEE CS Press, 1995. [9] B. Chazelle et al. The computational geometry impact task force report. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223, pages 407–463. AMS, 1999. [10] C.-Y. Chen, Y.-F. Hung, and H.-I Lu. Visibility representations of fourconnected plane graphs with near optimal heights. In Proc. of GD 2008, Lecture Notes in Computer Science. Springer, 2008. to appear. [11] G. Di Battista, P. Eades, R. Tammassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999. [12] G. Di Battista, R. Tamassia, and I. G. Tollis. Constrained visibility representations of graphs. Information Processing Letters, 41(1):1–7, 1992. [13] P. Eades. A heuristic for graph drawing. Congress Numerantium, 42:149–160, 1984. [14] P. Eades. Drawing free trees. Bulletin of the Institute for Combinatorics and its Applications, pages 10–36, 1992. [15] P. Eades and N. C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11:379–403, 1994. [16] U. Feige and R. Krauthgamer. A polylogarithmic approximation of the minimum bisection. SIAM Review, 48(1):99–130, 2006. [17] U. Feige and O. Yahalom. On the complexity of finding balanced oneway cuts. Information Processing Letters, 87(1):1–5, 2003. [18] M. Formann and F. Wagner. A packing problem with applications to lettering of maps. In Proc. of SoCG 1991, pages 281–288. ACM Press, 1991. [19] M. R. Garey and D. S. Johnson. Computers and Interactability. A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. Freemann And Company, 1979. [20] S. Grivet, D. Auber, J.P. Domenger, and G. Melan﹐con. Bubble tree drawing algorithm. In Proc. of International Conference on Computer Vision and Graphics 2004, pages 633–641, 2004. [21] X. He and H. Zhang. Nearly optimal visibility representations of plane graphs. In Proc. of ICALP 2006, volume 4051 of Lecture Notes in Computer Science, pages 407–418. Springer, 2006. [22] E. Imhof. Positioning names on maps. The American Cartographer, 2(2):128–144, 1975. [23] C. Iturriaga and A. Lubiw. NP-hardness of some map labeling problems. Technical Report CS-97-18, University of Waterloo, 1997. [24] C.-S. Jeong and A. Pang. Reconfigurable disc trees for visualizing large hierarchical information space. In Proc. of InfoVis 1998, pages 19–25. IEEE CS Press, 1998. [25] G. Kant. A more compact visibility representation. International Journal of Computational Geometry and Applications, 7:197–210, 1997. [26] M. Kaufmann and D. Wagner, editors. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer, 2001. [27] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291–307, 1970. [28] H. Koike and H. Yoshihara. Fractal approaches for visualizing huge hierarchies. In Proc. of VL 1993, pages 55–60. IEEE CS Press, 1993. [29] C.-Y. Lee and G. L. Vairaktarakis. Workforce planning in mixed model assembly systems. Operations Research, 45(4):553–567, 1997. [30] C.-C. Lin, H.-I Lu, and I.-F. Sun. Improved compact visibility representation of planar graph via Schnyder’s realizer. SIAM Journal on Discrete Mathematics, 18(3):19–29, 2004. [31] G. Melan﹐con and I. Herman. Circular drawing of rooted trees. Reports of the Centre for Mathematics and Computer Sciences, 1998. Report number INS-9817. [32] X. Munoz, W. Unger, and I. Vrt’o. One sided crossing minimization is NPhard for sparse graphs. In Proc. of GD 2001, volume 2265 of Lecture Notes in Computer Science, pages 115–123. Springer, 2002. [33] G. Neyer. Map labeling with application to graph drawing. In D. Wagner and M. Kaufman, editors, Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science, pages 247–273. Springer, 2001. [34] J. Nummenmaa. Constructing compact rectilinear planar layouts using canonical representation of planar graphs. Theoretical Computer Science, 99:213–230, 1992. [35] R. Otten and J. van Wijk. Graph representations in interactive layout design. In Proc. of ISCAS 1978, pages 914–918. IEEE Press, 1978. [36] H. C. Purchase. Metrics for graph drawing aesthetics. Journal of Visual Languages and Computing, 13(5):501–516, 2002. [37] E. Reingold and J. Tilford. Tidier drawing of trees. IEEE Transactions on Software Engineering, SE-7(2):223–228, 1981. [38] G. Robertson, J. Mackinlay, and S. Card. Cone trees: animated 3D visualizations of hierarchical information. In Proc. of CHI 1991, pages 189–194. ACM Press, 1991. [39] P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete and Computational Geometry, 1(4):343–353, 1986. [40] M. Schlag, F. Luccio, P. Maestrini, D. T. Lee, and C. K. Wong. A visibility problem in VLSI layout compaction. In F. P. Preparata, editor, Advances in Computing Research, volume II, pages 259–282. JAI Press, Greenwich, CT, 1985. [41] Y. Shiloach. Arrangements of planar graphs on the planar lattices. PhD thesis, Weizmann Instite of Science, 1976. [42] R. Tamassia and I.G.Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1:321–341, 1986. [43] J. J. Thomas and K. A. Cook, editors. Illuminating the Path: The R&D Agenda for Visual Analytics. IEEE CS Society, 2005. [44] G. L. Vairaktarakis. On Gilmore-Gomory’s open question for the bottleneck TSP. Operations Research Letters, 31(6):483–391, 2003. [45] F. Wagner. Approximate map labeling is in ω(n log n). Information Processing Letters, 52(3):161–165, 1994. [46] F.Wagner and A.Wolff. Map labeling heuristics: provably good and practically useful. In Proc. of SoCG 1995, pages 109–118. ACM Press, 1995. [47] A. Wolff and T. Strijk. The map-labeling bibliography. http://i11www.ira.uka.de/map-labeling/bibliography/, 1996. [48] Y. Ye. A .699-approximation algorithm for max-bisection. Mathematical Programming, 90(1):101–111, 2001. [49] H. Zhang and X. He. Compact visibility representation and straight-line grid embedding of plane graphs. In Proc. of WADS 2003, volume 2748 of Lecture Notes in Computer Science, pages 493–504. Springer, 2003. [50] H. Zhang and X. He. Improved visibility representation of plane graphs. Computational Geometry: Theory and Applications, 30(1):29–39, 2005. [51] H. Zhang and X. He. Visibility representation of plane graphs via canonical ordering tree. Information Processing Letters, 96:41–48, 2005. [52] H. Zhang and X. He. An application of well-orderly trees in graph drawing. International Journal of Foundations of Computer Science, 17(5):1129–1142, 2006. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41878 | - |
| dc.description.abstract | 隨著圖形在不同科學與工程領域中被獲知是最重要的抽象化結構之一，圖形繪製已冒出成為計算機科學中一個快速成長的研究主題。傳統的圖形繪製演算法被設計來遵循好的繪圖之一個或多個美學準則。本研究探討從最簡單到最複雜的三種圖形種類之二維繪圖上不同美學準則之最佳化。
首先、我們研究有根樹之氣球繪圖。在此種繪圖中，每一個子樹被繪製成包在一個圓形當中，而且角度的大小會嚴重地影響繪圖的清晰度。因此，本研究探討在不同氣球繪圖設定下不同角度測度之最佳化問題，其中包含了最佳化之角解析度、最大角與最小角之比率、和角度之標準差。另外，本研究還提供了在氣球繪圖上的幾個應用。 其次、我們研究雙層與三層網路繪圖(其中每一個結點分別被畫在兩條和三條垂直線上)及其應用在多對一邊界標示。在多對一邊界標示中，地圖上所有的標籤被置放在包圍著所有特徵點之矩形地圖的四邊上，其中一個以上的特徵點允許連接到共同的標籤，特徵點與標籤之間是用指線(可能是縱橫線段或直線段)所連接。本研究利用雙層與三層網路繪圖來解決在一些單邊與雙邊標示機制下之指線交叉數目最少化問題。更進一步地，我們用超指線換掉指線並採用傀儡標籤來設計完全沒有交叉的邊界標示法。 再次、我們研究平面圖之能見表示法。在此表示法中，每一個結點被畫成水平線段，使得對應到兩相連結點之兩條水平線段在垂直方向上彼此能見。給定一個n個結點之平面圖，本研究設計一個O(n)時間之演算法，來找出寬度不超過 之此平面圖之能見表示法。我們的結果在寬度上界達到最佳化，因為我們的寬度上界與過去已知最佳之寬度下界只差一單位。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T00:35:32Z (GMT). No. of bitstreams: 1 ntu-98-F89921122-1.pdf: 1913104 bytes, checksum: 18ccedb3772b01d0340226b1ae132eed (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | TABLE OF CONTENTS
頁次 口試委員會審定書 .................................................. i 謝辭 .................................................. ii 中文摘要 .................................................. iii Abstract .................................................. iv Chapter 1: Introduction .................................................. 1 1.1 Balloon Drawing of Rooted Trees .................................................. 2 1.2 Two- and Three- Layered Network Drawings with Application to Many-to-One Boundary Labeling .................................................. 5 1.3 Visibility Representations of Plane Graphs .................................................. 13 1.4 Organization of this Research .................................................. 14 Chapter 2: Balloon Drawings of Rooted Trees .................................................. 15 2.1 Preliminaries .................................................. 15 2.2 Case C1 (Unordered Trees with Even Sub-Wedges) .................................................. 21 2.3 Case C2 (Ordered Trees with Flexible Uneven Sub-Wedges) .................................................. 25 2.4 Cases C3 and C4 (Unordered Trees with Fixed/Flexible Uneven Sub-Wedges) .................................................. 27 2.5 Applications .................................................. 40 Chapter 3: Two- and Three- Layered Network Drawings with Application to Many-to-One Boundary Labeling .................................................. 42 3.1 Preliminaries .................................................. 42 3.2 The Crossing Problem for One-Side Many-to-One Labeling with Type-opo Leaders .................................................. 46 3.3 The Crossing Problem for Two-Side Many-to-One Labeling with Type-opo Leaders .................................................. 52 3.4 The Crossing Problem for One-Side Many-to-One Labeling with Type-po Leaders .................................................. 62 3.5 The Crossing Problem for Two-Side Many-to-One Labeling with Type-po Leaders .................................................. 66 3.6 Discussions .................................................. 70 3.7 Many-to-One Boundary Labeling Using Hyperleaders and Dummy Labels .................................................. 71 Chapter 4: Visibility Representations of Plane Graphs .................................................. 78 4.1 Preliminaries .................................................. 78 4.2 Our Results .................................................. 81 Chapter 5: Conclusions and Future Work .................................................. 115 References .................................................. 118 TABLE OF FIGURES Figure Number Page 1.1 Overview of this research .................................................. 2 1.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 1.3 The balloon drawings with even sub-wedges under two different tree orderings, where (b) achieves the optimality of RE1 and RA1 .................................................. 5 1.4 An example for labeling a server motherboard .................................................. 9 1.5 Other labeling approaches .................................................. 9 1.6 Illustration of leaders .................................................. 10 1.7 Illustration of boundary labeling with hyperleaders and dummy labels .................................................. 10 1.8 (a) A plane triangulation and (b) its visibility representation .................................................. 13 2.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.2 Notations used in a balloon drawing of a star graph with uneven sub-wedges .................................................. 16 2.3 An example for 2SAL and 2SLW .................................................. 20 2.4 An experimental result. (The above is its statistics.) .................................................. 25 2.5 An example showing how Algorithm 3 works .................................................. 33 2.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 2.7 Applications to galaxy systems and H-graphs .................................................. 41 3.1 A four-side many-to-one labeling with type-s leaders .................................................. 44 3.2 An example reducing from DCP to DMCP .................................................. 48 3.3 The first category of crossings .................................................. 48 3.4 The second category of crossings .................................................. 48 3.5 (a) A instance of two-layered network. (b) The boundary labeling corresponding to (a) .................................................. 48 3.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 3.7 The distribution of some animals in Taiwan, which is represented by one-side many-to-one labeling with type-opo leaders .................................................. 51 3.8 Two boundary labeling layouts with type-opo leaders for the same map .................................................. 52 3.9 G' (L_0', L_L', L_R', E') with |L_0'| = N + n(2 C^N_2 + 2) and L_R' = L1 .................................................. 55 3.10 The distribution of some animals in Taiwan, which is represented by two-side many-to-one labeling with type-opo leaders .................................................. 62 3.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 3.12 The experimental results for DCP1ML-po .................................................. 66 3.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 3.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 3.15 An example for illustrating how Algorithm 10 is executed .................................................. 69 3.16 The experimental results for DCP2ML-po .................................................. 70 3.17 The outputs of an example for each step in Algorithm 12 .................................................. 75 4.1 Illustration of the coalescing and splitting operations .................................................. 80 4.2 Illustration of L-shapes .................................................. 82 4.3 Six possible visibility drawings for a good face v_p v_q v_r .................................................. 83 4.4 The β_1 operation of node v_{k+1} executed at a right L-shape .................................................. 83 4.5 The β_2 operation of node v_{k+1} executed at two adjacent L-shapes .................................................. 83 4.6 The β_3 operation of node v_{k+1} executed at three adjacent L-shapes .................................................. 84 4.7 Intermediate steps of an example for Algorithm 13 .................................................. 86 4.8 Discussion of three possible pairs of input L-shapes of a β_3 operation .................................................. 92 4.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 4.10 Illustration of a μ_i operation for i >= 1 .................................................. 96 4.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 4.12 Illustration of subcase (a1) .................................................. 104 4.13 Illustration of subcase (a2) .................................................. 104 4.14 Illustration of a μ1 operation executed at face f_1, which is produced after executing a μ3 operation .................................................. 108 4.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 4.16 Illustration of how to adjust face f_1 to be good, when w_b(D_2(f_{k,1})) = 2 .................................................. 110 4.17 Illustration of how to adjust face f_1 to be good, when w_b(D_2(f_{k,1})) = 1 .................................................. 110 4.18 First μ_2 and then μ_1 operations can be viewed as first μ1 and then μ_3 operations .................................................. 111 4.19 Three possible cases of the drawing after executing a u_2 operation at a U-shape .................................................. 113 LIST OF TABLES Figure Number Page 1.1 The time complexity for optimizing main aesthetic criteria of balloon drawing .................................................. 6 1.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 4.1 The three pairs of the input L-shapes of the β_1, β_2, and β_3 operations .................................................. 91 | |
| dc.language.iso | en | |
| dc.subject | 能見表示法 | zh_TW |
| dc.subject | 圖形繪製 | zh_TW |
| dc.subject | 圖形演算法 | zh_TW |
| dc.subject | 氣球繪圖 | zh_TW |
| dc.subject | 邊界標示 | zh_TW |
| dc.subject | graph drawing | en |
| dc.subject | visibility representation | en |
| dc.subject | boundary labeling | en |
| dc.subject | balloon drawing | en |
| dc.subject | graph algorithm | en |
| dc.title | 不同美學準則之最佳化二維圖形繪製演算法 | zh_TW |
| dc.title | Optimizing Various Aesthetic Criteria in Two-Dimensional Graph Drawing | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-1 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 郭斯彥,雷欽隆,呂學一,莊仁輝,鍾國亮,黃秋煌,王柏堯 | |
| dc.subject.keyword | 圖形繪製,圖形演算法,氣球繪圖,邊界標示,能見表示法, | zh_TW |
| dc.subject.keyword | graph drawing,graph algorithm,balloon drawing,boundary labeling,visibility representation, | en |
| dc.relation.page | 122 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2008-12-30 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 1.87 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。