請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40952完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
| dc.contributor.author | Ya-Fei Hung | en |
| dc.contributor.author | 洪雅斐 | zh_TW |
| dc.date.accessioned | 2021-06-14T17:08:30Z | - |
| dc.date.available | 2008-07-30 | |
| dc.date.copyright | 2008-07-30 | |
| dc.date.issued | 2008 | |
| dc.date.submitted | 2008-07-26 | |
| dc.identifier.citation | [1] H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica,10:41–51, 1990.
[2] S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science,2(3):339–344, 1976. [3] J.-H. Fan, C.-C. Lin, H.-I. Lu, and H.-C. Yen. Width-optimal visibility representations of plane graphs. In Proceeding of the 18th Annual International Symposium on Algorithms and Computation,Lecture Notes in Computer Science 4835, pages 160–171, 2007. [4] X. He, M.-Y. Kao, and H.-I. Lu. Linear-time succinct encodings of planar graphs via canonical orderings. SIAM Journal on Discrete Mathematics, 12(3):317–325, 1999. [5] G. Kant. A more compact visibility representation. International Journal Computational Geometry and Applications, 7(3):197–210, 1997. [6] G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172:175–193, 1997. [7] C.-C. Lin, H.-I. Lu, and I.-F. Sun. Improved compact visibility representation of planar graph via Schnyder’s realizer. SIAM Journal on Discrete Mathematics, 18(1):19–29, 2004. [8] R. H. J. M. Otten and J. G. van Wijk. Graph representations in interactive layout design. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 914–918,1978. [9] P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete and Computational Geometry, 1:343–353, 1986. [10] R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1:321–341, 1986. [11] H. Zhang and X. He. Compact visibility representation and straight-line grid embedding of plane graphs. In Proceedings of the 8th International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 2748, pages 493–504, 2003. [12] H. Zhang and X. He. New theoretical bounds of visibility representation of plane graphs. In J. Pach, editor, Proceedings of the 12th International Symposium on Graph Drawing, Lecture Notes in Computer Science 3383, pages 425–430, 2004. [13] H. Zhang and X. He. On visibility representation of plane graphs. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 2996, pages 477–488, 2004. [14] H. Zhang and X. He. Canonical ordering trees and their applications in graph drawing. Discrete and Computational Geometry, 33:321–344, 2005. [15] H. Zhang and X. He. Improved visibility representation of plane graphs. Computational Geometry, 30(1):29–39, 2005. [16] H. Zhang and X. He. Nearly optimal visibility representations of plane graphs. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 4051, pages 407–418, 2006. [17] H. Zhang and X. He. Optimal st-orientations for plane triangulations. In Proceedings of the 3rd International Conference on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science 4508, pages 296–305, 2007. [18] H. Zhang and X. He. Nearly optimal visibility representations of plane triangulations. SIAM Journal on Discrete Mathematics, accepted upon minor revision, 2008 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/40952 | - |
| dc.description.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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-14T17:08:30Z (GMT). No. of bitstreams: 1 ntu-97-R94944014-1.pdf: 479363 bytes, checksum: 826917e7a23b07cc846b792c3a3209e5 (MD5) Previous issue date: 2008 | en |
| dc.description.tableofcontents | Acknowledgements.....i
Chinese Abstract.....ii English Abstract.....iii Contents.....iv List of Figures.....vi List of Tables.....vii 1 Introduction.....1 2 Preliminaries.....5 2.1 Ordering and st-ordering.....5 2.2 Four-canonical ordering.....6 2.3 Consistent ordering of ladder graph.....7 3 Our Algorithm.....9 3.1 Proving Theorem 1.1.....11 4 A lower bound on the required height.....15 Bibliography.....17 | |
| dc.language.iso | en | |
| dc.title | 四連接平面圖的可視性呈現之研究 | zh_TW |
| dc.title | Visibility Representations of Four-Connected Plane Graphs with Near Optimal Heights | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 96-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 徐讚昇(Tsan-Sheng Hsu),陳維美(Wei-Mei Chen) | |
| dc.subject.keyword | 平面圖,四連接圖,可視性,三角化,最佳化, | zh_TW |
| dc.subject.keyword | visibility representation,plane graph,four-connected,st-ordering,ladder graph, | en |
| dc.relation.page | 18 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2008-07-29 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
| 顯示於系所單位： | 資訊網路與多媒體研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-97-1.pdf 目前未授權公開取用 | 468.13 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。