Please use this identifier to cite or link to this item:
https://ah.lib.nccu.edu.tw/handle/140.119/56883
題名: | 探討平面圖的d維矩形表示法 A Study on Strict d-box Representations of Planar Graphs |
作者: | 劉淑慧 | 貢獻者: | 張宜武博士 劉淑慧 |
關鍵詞: | 區間圖 四連通三角平面圖 嚴格d維矩形表示法 interval graphs 4-connected planar triangulation graph strict d-box representation |
日期: | 2012 | 上傳時間: | 1-二月-2013 | 摘要: | 本文我們探討平面圖形的嚴格d維矩形表示法。我們證明了四連通三角平面圖有嚴格的二維矩形表示法,而且我們推廣到每一個平面圖都有嚴格的三維矩形表示法。我們的目標是希望能在平面圖矩形表示法的現今地位上,提供新的洞悉,並給未來學習者一個方向。 We study strict d-box representations of planar graphs. We prove that a 4-connected planar triangulation graph G has a strict 2-box representation. We extend this result to that every planar graph has a strict 3-box representation. Our goal is to provide some fresh insights into the current status of research in the area while suggesting directions for the future. |
參考文獻: | [1] P. Duchet, Y. Hamidoune, M. Las Vergas, and H. Meyniel, Representing a planar graph by vertical lines joing different levels, Discrete Math. 46(1983), 221-332.\n[2] L. A. Melnikov, Problem at the "Sixth Hungar. Colloq. on Combinatorics", Eger, 1981.\n[3] E. R. Scheinerman, "Intersection Classes and Multiple Intersection Parameters", Ph. D. thesis, Princetion Uni., 1984.\n[4] E. R. Scheinerman and D. B. West, "The interval number of a planar graph: Three intervals suffice, J. Combin. Theory Ser. B 35 (1983), 224-239.\n[5] C. Thomassen, Plane representations of graphs, in "Progress in Graph Theory", (J. A. Bondy and U. S. Murty, Eds.), pp.43-69, Academic Press, Toronto, 1984.\n[6] W. T. Trotter, Graphs and partially ordered sets, in "Selected Topics in Graph Theory 2", (L. W. Beineke and R. J. Wilson, Eds.), pp.237-268, Academic Press, London, 1983.\n[7] P. Unger, On diagrams representing maps, J. London Math. Soc. 28 (1953), pp.336-342\n[8] C. Thomassen, "Interval representations of planar graphs, Journal of Combinatorial Theory, Series B, pp.9-20, 1986. | 描述: | 碩士 國立政治大學 應用數學研究所 99972007 101 |
資料來源: | http://thesis.lib.nccu.edu.tw/record/#G0099972007 | 資料類型: | thesis |
Appears in Collections: | 學位論文 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
200701.pdf | 1.47 MB | Adobe PDF2 | View/Open |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.