Please use this identifier to cite or link to this item:

Title: 探討平面圖的d維矩形表示法
A Study on Strict d-box Representations of Planar Graphs
Authors: 劉淑慧
Contributors: 張宜武博士
Keywords: 區間圖
interval graphs
4-connected planar triangulation graph
strict d-box representation
Date: 2012
Issue Date: 2013-02-01 16:53:21 (UTC+8)
Abstract: 本文我們探討平面圖形的嚴格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.
Reference: [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.
Description: 碩士
Source URI:
Data Type: thesis
Appears in Collections:[應用數學系] 學位論文

Files in This Item:

File SizeFormat
200701.pdf1470KbAdobe PDF255View/Open

All items in 學術集成 are protected by copyright, with all rights reserved.

社群 sharing