請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38643
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 顏嗣鈞 | |
dc.contributor.author | Jia-Hao FAN | en |
dc.contributor.author | 范家豪 | zh_TW |
dc.date.accessioned | 2021-06-13T16:40:18Z | - |
dc.date.available | 2006-07-19 | |
dc.date.copyright | 2005-07-19 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-07-04 | |
dc.identifier.citation | [1] C.-C. Lin, H.-I. Lu, and I.-F. Sun, Improved compact visibility representation of planar graph via Schnyder's Realizer, in SIAM J Discrete Math, 2004. Vol. 18, No. 1, pp. 19-29.
[2] H. Zhang and X. He, Compact visibility representation and straight-line grid embedding of plane graphs, in: Proc. WADS’03, LNCS, Vol. 2748, Springer-Verlag Heidelberg, 2003 pp. 493-504. [3] G. Di Battista, R. Tamassia, and I. G. Tollis, Constrained visibility representations of graphs, Inform. Process. Lett., 41 1992, pp. 1–7. [4] M. Schlag, F. Luccio, P. Maestrini, D. T. Lee, and C. K. Wong, A visibility problem in VLSI layout compaction, in Advances in Computing Research, vol. 2, F. P. Preparata, ed., JAI Press, Greenwich, CT, 1985, pp. 259–282. [5] P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom., 1(4) 1986, pp. 343-353. [6]. R. Tamassia and I.G.Tollis, An unified approach to visibility representations of planar graphs. Discrete Comput. Geom. 1 1986, pp. 321-341. [7] G. Kant, A more compact visibility representation. International Journal of Computational Geometry and Applications 7 1997, pp. 197-210. [8] G. Kant and X. He, Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science 172 1997, pp. 175-193. [9] H. Zhang and X. He, On visibility representation of plane graphs, in: Proc. STACS’04, LNCS, Vol. 2996, Springer-Verlag Heidelberg, 2004 pp. 477-488. [10] Huaming Zhang and Xin He, New theoretical bounds of visibility representation of plane graphs, Graph Drawing, 12th International Symposium, GD 2004,.pp. 425-430. [11] R. Otten and J. van Wijk, Graph representations in interactive layout design, in Proceedings of the IEEE International Symposium on Circuits and Systems, 1978, pp. 914–918. [12] J. Nummenmaa, Constructing compact rectilinear planar layouts using canonical representation of planar graphs, Theoret. Comput. Sci., 99 1992, pp. 213–230. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38643 | - |
dc.description.abstract | 一個平面圖形的 visibility representation 是將圖的點表示成水平線,圖的線表示成垂直線. 如此表示平面圖的圖形的畫法,在圖的面積,長或寬度上有一定的限制.這篇論文我們是要解決他寛度最適的問題.我們找到了最適寛度的畫法 | zh_TW |
dc.description.abstract | 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) | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T16:40:18Z (GMT). No. of bitstreams: 1 ntu-94-R92921077-1.pdf: 324486 bytes, checksum: 1e85d7274857e9a8ef51475e77699d30 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | 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 49 | |
dc.language.iso | en | |
dc.title | 平面圖能見表示法的最適寛度 | zh_TW |
dc.title | Optimizing the Width of a Visibility Representation of Planar Graphs | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.coadvisor | 呂學一 | |
dc.contributor.oralexamcommittee | 王凡,雷欽隆,黃秋煌 | |
dc.subject.keyword | 圖論及演算法, | zh_TW |
dc.subject.keyword | graph drawing and graph algorithm,visibility representation,VLSI design, | en |
dc.relation.page | 49 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-07-04 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 316.88 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。