請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40952
標題: | 四連接平面圖的可視性呈現之研究 Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights |
作者: | Ya-Fei Hung 洪雅斐 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 平面圖,四連接圖,可視性,三角化,最佳化, visibility representation,plane graph,four-connected,st-ordering,ladder graph, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | A visibility representation of a graph G is to represent the nodes of G with non-overlapping horizontal line segments such that the line segments representing any two distinct adjacent nodes are vertically visible to each other. If G is a plane graph, i.e., a planar graph equipped with a planar embedding, a visibility representation of G has the additional requirement of reflecting the given planar embedding of G. For the case that G is an n-node four-connected plane graph, we give an O(n)-time algorithm to produce a visibility representation of G with height at most n/2+ O(sqrt(n)). To ensure that the first-order term of the upper bound is optimal, we also show an n-node four-connected plane graph G, for infinite number of n, whose visibility representations require heights at least n/2. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40952 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 468.13 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。