沒有任何連通度為四的平面圖形是一個可見圖

Abstract

可見圖的判斷問題是: 給一個圖形, 判斷這個圖形是否是一個多邊形的可 見圖. 到目前為止我們仍不知道這個問題是否能在多項式時間內解出 . 一個圖形是可見圖的必要條件是: 必須存在至少一個漢彌頓循環, 而這 漢彌頓循環恰對應至多邊形的邊界. 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.