跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

我願授權國圖
: 
twitterline
研究生:張以潤
研究生(外文):Chang
論文名稱:圖的接觸表示法
論文名稱(外文):Contact Representations of Graphs
指導教授:顏嗣鈞
指導教授(外文):Hsu-Chun Yen
口試委員:許聞廉呂學一于天立陳和麟
口試委員(外文):Wen-Lien HsuHsueh-I LuTian-Li YuHo-Lin Chen
口試日期:2015-06-29
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2015
畢業學年度:103
語文別:英文
論文頁數:131
中文關鍵詞:圖形繪製接觸表示法平面圖示意地圖平面規劃
外文關鍵詞:graph drawingcontact representationplanar graphcartogramfloorplan
相關次數:
  • 被引用被引用:0
  • 點閱點閱:149
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
圖(graph)是個常見的數學模型,能描述各種複雜的科學和工程問題。圖形繪製(Graph drawing)是將一個圖表示在二維或三維空間的過程,讓圖的結構以易於理解的方式呈現出來。由於這議題的重要性,圖形繪製已成為計算機科學中一個快速成長的新興領域。

在眾多圖形繪製的問題中,圖的接觸表示法(contact representations of graphs)在近年來受到的關注不斷提升。給定一個圖,它的接觸表示法即是將圖中的各個節點對應到二維或三維空間的幾何物件,其中任兩個節點在圖上相鄰若且唯若他們對應的物件互相接觸。

在許多接觸表示法中, rectilinear dual 是一個經典的繪製風格,能應用於大型積體電路的布圖規劃。在該繪製風格中,圖中的各個節點用正交多邊形來表示,多邊形的相鄰對應於節點在圖中的相鄰關係,並且所有的多邊形合起來恰好成為一個長方形。

在本論文的前半,我們探討如何在多邊形形狀被限制的情形下設計 rectilinear dual。因凸形(convex shapes) 傾向比非凸形來得好看且單純,我們提出並探討一個新的圖形繪製風格 - orthogonally convex drawing,研究如何設計 rectilinear dual 的演算法使得其中的幾何物件皆為正交凸多邊形(orthogonally convex polygons)。 另外,為了瞭解各形狀在繪製 rectilinear dual 中的功用與限制,我們探討可用形狀被限制下的rectilinear dual。 我們算出 T-free rectilinear dual 的多邊形複雜度,驗證了 T 形是最有用的八邊形之直覺。

在本論文的後半,我們探討如何將 rectilinear dual 延伸及推廣到二維正交以外的情境上。為了容納凸多邊形(convex polygons),我們提出並探討一個新的圖形繪製風格 - convex polygonal dual。 針對這項繪製風格,我們提出一些新的技術及fixed-parameter tractability 的結果。為了容納正交多面體(orthogonal polyhedra),我們提出並探討一個新的圖形繪製風格 - 3D floorplan。我們證明了所有 chordal graph 都能畫成 3D-floorplan。 我們的畫法不但只需用到兩層,也能夠實現任意對其中多面體指定的體積。

總體來說,在圖的接觸表示法之框架下,本論文提供了許多新的技術及觀點。希望這篇論文指引出的研究方向能讓我們對這個充滿挑戰性的領域有更全面的認識。

Graph represents one of the most popular abstract models in describing complex science and engineering problems. Graph drawing refers to the process of displaying an abstract graph in 2D or 3D, allowing the structure as well as the meaning of the graph to be understood better and easier. As a consequence, the design of graph drawing algorithms has become an emerging and fast growing research area in computer science.

Among problems of interest in the graph drawing community, the topic of contact representations of graphs has received increasing attention over the years. Given a graph, a contact representation of the graph is to map each vertex of the graph to a geometric object in 2D or 3D so that two vertices are adjacent iff their corresponding objects "touch".

A rectilinear dual, a classic drawing style which has found applications in VLSI floor-planning, requires that each vertex be drawn as a rectilinear polygon, adjacency in a graph correspond to side-contact in the drawing, and all rectilinear polygons together form a partition of a rectangle.

In the first half of the thesis, we investigate a variety of shape constraints in rectilinear duals. As convex objects tend to be visually more pleasing, the drawing style orthogonally convex drawing is proposed and investigated. In addition, we study rectilinear duals using a restricted set of shapes, in order to understand the power and the limitation of different shapes in rectilinear duals. We determine the optimal polygonal complexity of T-free rectilinear dual, justifying the intuition that T-shape is the most useful 8-sided polygon.

In the second half of the thesis, we study possible extensions and generalizations of rectilinear duals beyond the 2D rectilinear setting. To accommodate convex polygons, the drawing style convex polygonal dual is proposed and investigated. We demonstrate several new techniques and fixed-parameter tractability results to deal with this drawing style. We also propose and investigate a new drawing style called 3D floorplan, using rectilinear polyhedra as building blocks. We show that every chordal graph admits a 3D-floorplan which uses only two layers and is also capable of realizing any volume-assignment to its constituent polyhedra.

In summary, the thesis provides a variety of new techniques and new perspectives within the framework of contact representations of graphs. We hope that this study could lead to a better understanding of contact graph representations - an exciting and challenging topic in graph drawing.


口試委員會審定書 i
致謝 ii
中文摘要 iii
Abstract iv
Contents vi
List of Figures ix

1 Introduction 1

2 Preliminaries 7
2.1 Graph Theoretic Preliminaries . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Tree-width and Chordal Graphs . . . . . . . . . . . . . . . . . . . . . 9
2.3 Rectilinear Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Separation Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Sliceability and Area-universality . . . . . . . . . . . . . . . . . . . . 16
2.6 Other Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Orthogonally Convex Drawings 21
3.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Review of the Results of Rahman and Nishizeki . . . . . . . . . . . . . 25
3.4 No-bend Orthogonally Convex Drawings . . . . . . . . . . . . . . . . 27
3.5 An Alternative Condition . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6 Flow Formulation for Bend-minimization . . . . . . . . . . . . . . . . 40
3.7 Orthogonal Convexity in Rectilinear Duals . . . . . . . . . . . . . . . 47

4 Rectilinear Duals without T-shape 56
4.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Lower Bound of Polygonal Complexity . . . . . . . . . . . . . . . . . 58
4.3 Construction of 12-sided ⊤-free Rectilinear Duals . . . . . . . . . . . 60
4.3.1 Un-contracting a Separating Triangle . . . . . . . . . . . . . . 60
4.3.2 Transferring Concave Corners . . . . . . . . . . . . . . . . . . 64
4.4 Area-universal Drawings . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 More about Staircase Polygons . . . . . . . . . . . . . . . . . . . . . . 69

5 Convex Polygonal Duals 73
5.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3 Characterizing t-sided Convex Polygonal Duals . . . . . . . . . . . . . 76
5.4 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.5 Fixed-parameter Tractability Results . . . . . . . . . . . . . . . . . . . 88
5.6 Exact Definition of the Formula t-ValidFAA . . . . . . . . . . . . . . 92
5.6.1 t-FAA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.6.2 t-ValidFAA . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6.3 Remaining Formulas . . . . . . . . . . . . . . . . . . . . . . . 96
5.7 Further Applications of Our Technique . . . . . . . . . . . . . . . . . 100

6 Area-universal Drawings of Biconnected Outerplane Graphs 104
6.1 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.2 Drawing Biconnected Outerplane Graphs . . . . . . . . . . . . . . . . 105

7 3D Floorplans 112
7.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2 The Drawing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 113

8 Conclusion and Future Perspectives 121

Bibliography 126


[1] Nieke Aerts. Geometric Representations of Planar Graphs. PhD thesis, Technischen Universität Berlin, 2015.

[2] Nieke Aerts and Stefan Felsner. Straight line triangle representations. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 119--130. Springer International Publishing, 2013.

[3] Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, and Stephen G. Kobourov. Linear-time algorithms for hole-free rectilinear proportional contact graph representations. Algorithmica, 67(1):3--22, 2013.

[4] Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, and Torsten Ueckerdt. Computing cartograms with optimal complexity. Discrete & Computational Geometry, 50(3):784--810, 2013.

[5] Md. Jawaherul Alam, Stephen G. Kobourov, Giuseppe Liotta, Sergey Pupyrev, and Sankar Veeramoni. 3d proportional contact representations of graphs. In The 5th International Conference on Information, Intelligence, Systems and Applications (IISA 2014), pages 27--32, 2014.

[6] Giuseppe Di Battista, Giuseppe Liotta, and Francesco Vargiu. Spirality and optimal orthogonal drawings. SIAM Journal on Computing, 27(6):1764--1811, 1998.

[7] Michael A. Bekos, Michael Kaufmann, Robert Krug, Stefan Näher, and Vincenzo Roselli. Slanted orthogonal drawings. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 424--435. Springer International Publishing, 2013.

[8] Therese Biedl and Lesvia Elena Ruiz Velázquez. Orthogonal cartograms with few corners per face. In Frank Dehne, John Iacono, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, volume 6844 of Lecture Notes in Computer Science, pages 98--109. Springer Berlin Heidelberg, 2011.

[9] Yi-Jun Chang and Hsu-Chun Yen. On orthogonally convex drawings of plane graphs. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 400--411. Springer International Publishing, 2013.

[10] Yi-Jun Chang and Hsu-Chun Yen. Rectilinear duals using monotone staircase polygons. In Zhao Zhang, Lidong Wu, Wen Xu, and Ding-Zhu Du, editors, Combinatorial Optimization and Applications, volume 8881 of Lecture Notes in Computer Science, pages 86--100. Springer International Publishing, 2014.

[11] Yi-Jun Chang and Hsu-Chun Yen. A new approach for contact graph representations and its applications. To be presented in the 14th Algorithms and Data Structures Symposium (WADS''15), LNCS 9214, 2015.

[12] Sabine Cornelsen and Andreas Karrenbauer. Accelerated bend minimization. In Marc van Kreveld and Bettina Speckmann, editors, Graph Drawing, volume 7034 of Lecture Notes in Computer Science, pages 111--122. Springer Berlin Heidelberg, 2012.

[13] Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12--75, 1990.

[14] Bruno Courcelle and Engelfriet Joost. Graph Structure and Monadic SecondOrder Logic: A Language-Theoretic Approach. Cambridge University Press, 2012.

[15] Hubert de Fraysseix and Patrice Ossona de Mendez. Barycentric systems and stretchability. Discrete Applied Mathematics, 155(9):1079 -- 1095, 2007.

[16] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer-Verlag London, 2013.

[17] Christian A. Duncan, Emden R. Gansner, Yifan Hu, Michael Kaufmann, and Stephen G. Kobourov. Optimal polygonal representation of planar graphs. Algorithmica, 63(3):672--691, 2012.

[18] Christian A. Duncan and Michael T. Goodrich. Planar orthogonal and polyline drawing algorithms. In Handbook of Graph Drawing and Visualization, chapter 7. CRC Press.

[19] David Eppstein, Elena Mumford, Bettina Speckmann, and Kevin Verbeek. Areauniversal and constrained rectangular layouts. SIAM Journal on Computing, 41(3): 537--564, 2012.

[20] William Evans, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Debajyoti Mondal, Rahnuma Islam Nishat, and Kevin Verbeek. Table cartograms. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms – ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 421--432. Springer Berlin Heidelberg, 2013.

[21] J. Joseph Fowler. Strongly-connected outerplanar graphs with proper touching triangle representations. In Stephen Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 155--160. Springer International Publishing, 2013.

[22] Emden R. Gansner, Yifan Hu, and Stephen G. Kobourov. On touching triangle graphs. In Ulrik Brandes and Sabine Cornelsen, editors, Graph Drawing, volume 6502 of Lecture Notes in Computer Science, pages 250--261. Springer Berlin Heidelberg, 2011.

[23] Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM Journal on Computing, 31(2):601--625, 2001.

[24] Paul Horn and Gabor Lippner. Two layer 3d floor planning. The Electronic Journal of Combinatorics, 20(4):P16, 2013.

[25] Bapi Kar, Susmita Sur-Kolay, Sridhar H. Rangarajan, and Chittaranjan R. Mandal. A faster hierarchical balanced bipartitioner for vlsi floorplans using monotone staircase cuts. In Hafizur Rahaman, Sanatan Chattopadhyay, and Santanu Chattopadhyay, editors, Progress in VLSI Design and Test, volume 7373 of Lecture Notes in Computer Science, pages 327--336. Springer Berlin Heidelberg, 2012.

[26] Akifumi Kawaguchi and Hiroshi Nagamochi. Drawing slicing graphs with face areas. Theoretical Computer Science, 410(11):1061--1072, 2009.

[27] Gunnar W. Klau and Petra Mutzel. Quasi–orthogonal drawing of planar graphs. Technical Report MPI-I-98-1-013, Max-Planck-Institut für Informatik, Saarbrücken, 1998.

[28] Stephen G. Kobourov, Debajyoti Mondal, and Rahnuma Islam Nishat. Touching triangle representations for 3-connected planar graphs. In Walter Didimo and Maurizio Patrignani, editors, Graph Drawing, volume 7704 of Lecture Notes in Computer Science, pages 199--210. Springer Berlin Heidelberg, 2013.

[29] Paul Koebe. Kontaktprobleme der konformen abbildung. Ber. Verh. Sächs. Akademie der Wissenschaften Leipzig, Math.-Phys., Klasse 88:141--164, 1936.

[30] Krzysztof Koźmiński and Edwin Kinnen. Rectangular duals of planar graphs. Networks, 15(2):145--157, 1985.

[31] Chien-Chih Liao, Hsueh-I Lu, and Hsu-Chun Yen. Compact floor-planning via
orderly spanning trees. J. Algorithms, 48(2):441--451, 2003.

[32] Subhashis Majumder, Susmita Sur-Kolay, Bhargab B. Bhattacharya, and Swarup Kumar Das. Hierarchical partitioning of vlsi floorplans by staircases. ACM Trans. Des. Autom. Electron. Syst., 12(1):7:1--7:19, 2007.

[33] Kazuyuki Miura, Hiroki Haga, and Takao Nishizeki. Inner rectangular drawings of plane graphs. International Journal of Computational Geometry & Applications, 16(02n03):249--270, 2006.

[34] Takao Nishizeki and Md. Saidur Rahman. Planar Graph Drawing, Lecture Notes Series on Computing 12. World Scientific, 2004.

[35] Md. Saidur Rahman, Shinichi Nakano, and Takao Nishizeki. A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs. J. Graph Algorithms Appl, 3:31--62, 1999.

[36] Md. Saidur Rahman, Takao Nishizeki, and Mahmuda Naznin. Orthogonal drawings of plane graphs without bends. Journal of Graph Algorithms and Applications, 7(4):335--362, 2003.

[37] Md.Saidur Rahman, Noritsugu Egi, and Takao Nishizeki. No-bend orthogonal drawings of series-parallel graphs. In Patrick Healy and Nikola S. Nikolov, editors, Graph Drawing, volume 3843 of Lecture Notes in Computer Science, pages 409--420. Springer Berlin Heidelberg, 2006.

[38] Walter Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA''90, pages 138--148, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics.

[39] Jonathan Stott, Peter Rodgers, Juan Carlos Martínez-Ovando, and Stephen G. Walker. Automatic metro map layout using multicriteria optimization. Visualization and Computer Graphics, IEEE Transactions on, 17(1):101--114, 2011.

[40] Yachyang Sun and Majid Sarrafzadeh. Floorplanning by graph dualization: L shaped modules. In IEEE International Symposium on Circuits and Systems, volume 4, pages 2845--2848, 1990.

[41] Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16(3):421--444, 1987.

[42] Carsten Thomassen. Plane representations of graphs. In J.A. Bondy and U.S.R. Murty, editors, Progress in Graph Theory, pages 43--69. Academic Press, Toronto, 1984.

[43] Torsten Ueckerdt. Geometric Representations of Graphs with Low Polygonal Complexity. PhD thesis, Technischen Universität Berlin, 2011.

[44] Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2nd edition, 2001.

[45] Kok-Hoo Yeap and Majid Sarrafzadeh. Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM Journal on Computing, 22(3):500--526, 1993.


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