請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/4594完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞(Hsu-Chun Yen) | |
| dc.contributor.author | Hsuan-Yin Tsai | en |
| dc.contributor.author | 蔡萱尹 | zh_TW |
| dc.date.accessioned | 2021-05-14T17:43:51Z | - |
| dc.date.available | 2015-08-05 | |
| dc.date.available | 2021-05-14T17:43:51Z | - |
| dc.date.copyright | 2015-08-05 | |
| dc.date.issued | 2015 | |
| dc.date.submitted | 2015-08-03 | |
| dc.identifier.citation | [1] Evmorfia N. Argyriou, Michael A. Bekos, Antonios Symvonis. Maximizing the Total Resolution of Graphs. 18th Graph Drawing International Symposium, pages 62-67, 2010.
[2] Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seokhee Hong, Michael Kaufmann, Martin Nぴollenburg, Ignaz Rutter, and Antonios Symvonis. Many-to-One Boundary Labeling with Backbones. 21st Graph Drawing International Symposium, pages 244-255, 2013. [3] Michael A. Bekos, Michael Kaufmann, Michael Kaufmann, Antonios Symvonis. Boundary Labeling with Octilinear Leaders. Journal of Algorithmica, vol. 57, pages 436–461, 2010. [4] Francois Bertault and Peter Eades. Drawing Hypergraphs in the Subset Standard. In Proceedings of 8th Graph Drawing International Symposium, pages 164-169, 2000. [5] Michael Baur and Ulrik Brandes. Crossing Reduction in Circular Layouts. 30th Graph-Theoretic Concepts in Computer Science International Workshop, pages 332-343, 2004. [6] Walter Didimo, Peter Eades, Giuseppe Liotta. Drawing Graphs with Right Angle Crossings. In Proceedings of 11th Workshop on Algorithms and Data Structures, pages 206-217, 2009. [7] Thomas Eschbach, Wolfgang Gぴunther, Bernd Becker. Orthogonal Hypergraph Drawing for Improved Visibility. Journal of Graph Algorithms and Applications, vol. 10, pages 141-157, 2006. [8] Thomas M. J. Fruchterman, Edward M. Reingold. Graph drawing by force-directed placement. Journal Software—Practice & Experience archive Vol. 21, pages 1129 - 1164, 1991. [9] Emden R. Gansner, Yehuda Koren. Improved Circular Layouts. 14th Graph Drawing International Symposium, pages 386-398, 2006. [10] Martin Junghans. Visualization of Hyperedges in Fixed Graph Layouts. Master thesis of Brandenburg University of Technology Cottbus, 2008. [11] Michael Kaufmann, Marc van Kreveld, and Bettina Speckmann. Subdivision Drawings of Hypergraphs. 16th Graph Drawing International Symposium, pages 396-407, 2008. [12] Erkki Mäkinen. How to Draw a Hypergraph. International Journal of Computer Mathematics, vol. 34, pages 177-185, 1990. [13] Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, and Toshio fujisawa. Crossing Minimization in Linear Embeddings of Graphs. IEEE Transactions on Computers,vol. 39, pages 124–127, 1990. [14] Georg Sander. Layout of Directed Hypergraphs with Orthogonal Hyperedges. 11th Graph Drawing International Symposium, pages 381-386, 2003. [15] Sergey Pupyrev, Lev Nachmanson, Michael Kaufmann. Improving Layered Graph Layouts with Edge Bundling. 18th Graph Drawing International Symposium, pages 329-340, 2010. [16] C. Walshaw. A Multilevel Algorithm for Force-Directed Graph Drawing. In Proceedings of 8th Graph Drawing International Symposium, pages 171-182, 2000. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/4594 | - |
| dc.description.abstract | 此篇論文主要在探討超圖繪製在每條超邊都有連接著一條骨架的情況下，三種美觀標準的最佳化。而三種美觀標準分別為交叉數的最小化、超邊總長度的最小化、以及在超邊互不重疊的情況下，最大數目的超邊放置量。在交叉數的最小化方面，如果有一定的順序，則可以用動態規劃演算法求解。在超邊總長度最小化方面，可以將問題轉換成 bipartite matching 去求解。另外，在超邊放置最大量方面，則用貪婪法求解。此篇論文在骨架類型方面，包含有僅有水平骨架的超圖類型、同時有水平與垂直骨架的超圖類型，以及同時有水平、垂直、斜45度角水平骨架的超圖類型。 | zh_TW |
| dc.description.abstract | The thesis mainly discusses various optimization problems with respect to three aesthetic criteria in hypergraph drawings under the condition that each hyperedge has one backbone. The aesthetic criteria include minimizing the number of crossings, the total hyperedge length, and maximizing the number of hyperedges under the condition that a hypergraph has no overlapping hyperedge. In the aspect of crossings minimization, if there is an order among the hyperedges, we can use a dynamic programming algorithm to solve it. In the aspect of total length minimization, we transform the problem into the bipartite matching problem to solve it. In the aspect of maximizing the number of hyperedges, a greedy algorithm is proposed. Also, the thesis considers three different types of backbones: with horizontal backbones only, with both horizontal and vertical backbones, and allowing horizontal, vertical and octilinear horizontal backbones. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-14T17:43:51Z (GMT). No. of bitstreams: 1 ntu-104-R02921040-1.pdf: 1333752 bytes, checksum: 9528c977404474192630165a4115f80d (MD5) Previous issue date: 2015 | en |
| dc.description.tableofcontents | 口試委員會審定書…………………………………………………. i
誌謝…………………………………………………………………. ii 中文摘要……………………………………………………………. iii 英文摘要……………………………………………………………. iv 目 錄Contents……………………………………………………. v List of Figures………………………………………………………. vii List of Tables…………………………….………………………. ix 第一章 Introduction………………………………………………… 1 第二章Preliminary 2.1 Notation of Hypergraphs…………………………………. 4 2.2 Aesthetic Criteria……………………………………………. 6 2.3 Problem Description………………………………………… 8 第三章 Algorithm Model ---- Horizontal backbones 3.1 Crossings Minimization………………………………. 9 3.2 Length Minimization………………………………………. 14 3.3 Hyperedge Maximization…………………………………. 18 第四章 Algorithm Model ---- Vertical and horizontal backbones 4.1 Crossings Minimization 4.1.1 Hypergraph with Specified backbone …………………21 4.1.2 Hypergraph with Unspecified backbone……………….24 4.2 Length Minimization…………………………………….26 4.3 Hyperedge Maximization……………………………….28 第五章 Algorithm Model ---- Octilinear backbones 5.1 Crossings Minimization 5.1.1 Hypergraph with Fixed octilinear segment length ……32 5.1.2 Hypergraph with Flexible octilinear segment length….35 5.2 Length Minimization…………………………………………….38 5.3 Hyperedge Maximization……………………………………….41 第六章 Conclusion and Future Work………………………….43 參考文獻……………………………………………………….44 | |
| 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 | backbone | en |
| dc.subject | length minimization | en |
| dc.subject | crossing minimization | en |
| dc.subject | hypergraph | en |
| dc.title | 具骨架的超圖繪製 | zh_TW |
| dc.title | Hypergraph Drawing with Backbones | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 103-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 雷欽隆(Chin-Laung Lei),黃秋煌,莊仁輝 | |
| dc.subject.keyword | 圖形繪製,超圖,交叉數最小化,總長度最小化,骨架, | zh_TW |
| dc.subject.keyword | graph drawing,hypergraph,crossing minimization,length minimization,backbone, | en |
| dc.relation.page | 45 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2015-08-04 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf | 1.3 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。