Abstract
在計算機的領域裡，圖形是一種容易敘述卻很難解決的問題，許多難題轉化到圖形問題上就能以比較簡單的方式敘述並解決。好的資料結構以及有效率的演算法，方能快速的解決圖形上的問題。經由之前的研究人員的辛苦耕芸之下，許多方便以及有效的演算法得以順利的發展出來，為圖形的問題尋得最佳的解決方法。其中亦留下了不少可以繼續改進的演算法。本篇論文即是希望藉由以前的研究成果能在平面圖相關問題上找到較佳的解決方式。平面圖的偵測在許多應用領域裡是相當具有價值的，例如VLSI中的線路配置問題：在佈線之前如果可以先偵測圖形的平面性就可以減少不必要的成本花費；化學成份的同構性質(isomorphic)分析：如果知道此成份的化學結構為平面圖形，就可以簡化分析的過程等等。所以快速的演算法可以加快這些應用問題的執行速度並簡化複雜性。本篇論文中所提到的演算法的觀念是使用加點的方式(vertex addition)，依據石維寬先生和許聞廉先生所提出的標記法(Labeling)及terminal node的想法設計一個演算法可以快速偵測一些非平面圖的情形，此演算法所使用的資料結構非常簡單而且對於平面圖的表現法(planar embedding)來說，可以觀察平面圖的一些特性找出幾個規則，加入這些規則以後可以達到平面圖偵測與平面圖表現法同時完成的目的，最重要的是此演算法保證可以於線性時間內完成，達到最佳化的演算法。