請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38643
標題: | 平面圖能見表示法的最適寛度 Optimizing the Width of a Visibility Representation of Planar Graphs |
作者: | Jia-Hao FAN 范家豪 |
指導教授: | 顏嗣鈞 |
關鍵字: | 圖論及演算法, graph drawing and graph algorithm,visibility representation,VLSI design, |
出版年 : | 2005 |
學位: | 碩士 |
摘要: | 一個平面圖形的 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) |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38643 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 316.88 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。