平面可見圖及其性質之研究

Abstract

對一個簡單多邊形Ｐ的兩個頂點而言，如果連接這兩個頂點的封閉線段不 落在簡單多邊形Ｐ的外部（此線段可能會通過多邊形中其他的點，這是允 許的。），則稱這兩個點為互相看得見。對一個圖Ｇ而言，如果存在一個 簡單多邊形Ｐ，使得圖Ｇ中的點與簡單多邊形Ｐ的頂點一一對應，而且圖 Ｇ中的兩個點有邊相連的充要條件是它們在簡單多邊形Ｐ中所對應的兩個 頂點為互相看得見，則稱圖Ｇ為可見圖。在第三篇參考文獻中。Coullard 與Lubiw 證明了每個連通度為３的平面可見圖都可將它的點排成某個次序 ，使得每個點都至少與某３個序號在自己前面且兩兩相連的點相連。藉由 這個結果，在第一篇參考文獻中，Abello，Lin 與Pisupati證明了每個連 通度為３的平面可見圖一定是最大平面圖，而且沒有任何連通度為４的平 面圖是可見圖。非常不幸地，第一篇與第三篇參考文獻皆使用”非標準” 的可見圖定義；亦即他們主張連接兩個互相看得見的點之線段不得通過多 邊形中其他的點。在本論文中，我們將第一篇及第三篇參考文獻的結果推 廣至〞標準〞的可見圖定義。我們並且說明：每個平面可見圖都是弦圖。