標題: 沒有任何連通度為四的平面圖形是一個可見圖
No 4-Connected Planar Graph Could Be a Visibility Graph
作者: 林修懿
Lin, Shiou-Yi
陳秋媛
Chen, Chiuyuan
應用數學系所
關鍵字: 計算幾何學,可見的,可見圖,平面圖;Computational geometry,visibility ,visibility graph,planar graph
公開日期: 1992
摘要: 可見圖的判斷問題是: 給一個圖形, 判斷這個圖形是否是一個多邊形的可 見圖. 到目前為止我們仍不知道這個問題是否能在多項式時間內解出 . 一個圖形是可見圖的必要條件是: 必須存在至少一個漢彌頓循環, 而這 漢彌頓循環恰對應至多邊形的邊界. Tutte 證明了每一個連通度為四的平 面圖形都有漢彌頓循環, 但是在這篇論文裡我們將證明: 沒有任何連通度 為四的平面圖形會是一個可見圖. 此外我們也提出了一個多邊形具有平面 可見圖的充分必要條件. The recognition problem for visibility graphs is, given a graph, to determine whether this graph is the visibility graph of a simple polygon. It is not known whether this problem could be solved in polynomial time. A necessary condition for a graph to be a visibility graph is the existence of at least one Hamiltonian cycle, corresponding to the boundary of the polygon. Tutte proved that every 4-connected planar graph has a Hamiltonian cycle. However, in this thesis we shall prove that no 4-connected planar graph could be a visibility graph. We shall also give the necessary and sufficient conditions for a polygon to have a planar visibility graph.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT810507023
http://hdl.handle.net/11536/57126
Appears in Collections:Thesis