Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40952
Title: | 四連接平面圖的可視性呈現之研究 Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights |
Authors: | Ya-Fei Hung 洪雅斐 |
Advisor: | 呂學一(Hsueh-I Lu) |
Keyword: | 平面圖,四連接圖,可視性,三角化,最佳化, visibility representation,plane graph,four-connected,st-ordering,ladder graph, |
Publication Year : | 2008 |
Degree: | 碩士 |
Abstract: | 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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊網路與多媒體研究所 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-97-1.pdf Restricted Access | 468.13 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.