顏嗣鈞臺灣大學：電機工程學研究所范家豪FAN, Jia-HaoJia-HaoFAN2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53174一個平面圖形的 visibility representation 是將圖的點表示成水平線,圖的線表示成垂直線. 如此表示平面圖的圖形的畫法,在圖的面積,長或寬度上有一定的限制.這篇論文我們是要解決他寛度最適的問題.我們找到了最適寛度的畫法In a visibility representation of a planar graph G, each node of G is represented by a horizontal segment and each edge of G is represented by a vertical segment, and incidence between nodes and edges translates to intersection of horizontal and vertical segments. The grid size is at most (2n - 4)*(n - 1) for a graph with n nodes. G must not contain self-loops or multiple edges. We find an algorithm to draw a general planar graph to its visibility representation with width 4n/3 in O(n). More specifically, for an n-node planar graph G, we can obtain its 6 visibility drawings from a 3-node triangle’s 6 visibility drawings by applying a sequence of operations, and the sum of the widths of the six visibility representation of an n-node planar graph is 8n + O(1). Clearly there is at least one visibility representation among the six with the width smaller than 4n / 3 + O(1)1 Introduction 3 2 Preliminaries 5 2.1 vertex insertion framework 6 2.2 plane triangular decomposition 7 2.3 The minimum degree of a planar triangulation 10 2.4 The three operation pi1, pi2 and pi3 11 2.5 Six visibility drawings of an n-node plane triangulation 15 3 An algorithm for obtaining the optimal width of a visibility representation of planar graphs. 18 3.1 Operation pi1 18 3.2 Operation pi2 26 3.3 Operation pi3 46 References 49324486 bytesapplication/pdfen-US圖論及演算法graph drawing and graph algorithmvisibility representationVLSI designthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53174/1/ntu-94-R92921077-1.pdf