簡易檢索 / 詳目顯示
| 研究生： |
劉淑慧 |
|---|---|
| 論文名稱： |
探討平面圖的d維矩形表示法 A Study on Strict d-box Representations of Planar Graphs |
| 指導教授： | 張宜武博士 |
| 學位類別： |
碩士
Master |
| 系所名稱： |
理學院 - 應用數學系數學教學碩士在職專班 |
| 論文出版年： | 2013 |
| 畢業學年度： | 101 |
| 語文別： | 英文 |
| 論文頁數： | 27 |
| 中文關鍵詞： | 區間圖 、四連通三角平面圖 、嚴格d維矩形表示法 |
| 外文關鍵詞： | interval graphs, 4-connected planar triangulation graph, strict d-box representation |
| 相關次數： | 點閱：189 下載：7 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本文我們探討平面圖形的嚴格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 Introduction ...........................................1
2 Strict 2-box representation.............................4
2.1 Defitions and theprem of cyclically 4-edge-connected
planar graphs and 4-connected planar triangulation....4
graphs
2.2 Planar graphs have strict a 2-box representations by at
least two boxes.......................................8
3 Some results on d-box representation...................10
3.1 A strict 2-box representation for 4-connected planar
triangulation graphs.................................10
3.2 A strict 3-box representation for planar graphs......18
4 Open problems and further directions on study..........23
Reference................................................24
[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.
[2] L. A. Melnikov, Problem at the "Sixth Hungar. Colloq. on Combinatorics", Eger, 1981.
[3] E. R. Scheinerman, "Intersection Classes and Multiple Intersection Parameters", Ph. D. thesis, Princetion Uni., 1984.
[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.
[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.
[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.
[7] P. Unger, On diagrams representing maps, J. London Math. Soc. 28 (1953), pp.336-342
[8] C. Thomassen, "Interval representations of planar graphs, Journal of Combinatorial Theory, Series B, pp.9-20, 1986.
