跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/03 19:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蔡萱尹
研究生(外文):Hsuan-Yin Tsai
論文名稱:具骨架的超圖繪製
論文名稱(外文):Hypergraph Drawing with Backbones
指導教授:顏嗣鈞
指導教授(外文):Hsu-Chun Yen
口試委員:雷欽隆黃秋煌莊仁輝
口試委員(外文):Chin-Laung Lei
口試日期:2015-07-24
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:45
中文關鍵詞:圖形繪製超圖交叉數最小化總長度最小化骨架
外文關鍵詞:graph drawinghypergraphcrossing minimizationlength minimizationbackbone
相關次數:
  • 被引用被引用:0
  • 點閱點閱:116
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
此篇論文主要在探討超圖繪製在每條超邊都有連接著一條骨架的情況下,三種美觀標準的最佳化。而三種美觀標準分別為交叉數的最小化、超邊總長度的最小化、以及在超邊互不重疊的情況下,最大數目的超邊放置量。在交叉數的最小化方面,如果有一定的順序,則可以用動態規劃演算法求解。在超邊總長度最小化方面,可以將問題轉換成 bipartite matching 去求解。另外,在超邊放置最大量方面,則用貪婪法求解。此篇論文在骨架類型方面,包含有僅有水平骨架的超圖類型、同時有水平與垂直骨架的超圖類型,以及同時有水平、垂直、斜45度角水平骨架的超圖類型。

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.

口試委員會審定書…………………………………………………. 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


[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.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top