臺灣大學: 電機工程學研究所顏嗣鈞劉濟賢Liu, Chi-HsienChi-HsienLiu2013-03-272018-07-062013-03-272018-07-062012http://ntur.lib.ntu.edu.tw//handle/246246/254115圖繪製問題的答案，可以看作是由兩個部份所組成，分別是點的位置和邊的路徑。這兩個部份並非互相獨立，而必須一起考慮才能繪製出一張可讀性較高的圖。但是圖繪製的複雜度，就算簡化成只需要最小化邊交叉數目的問題，也已經證實是NP-complete [1]。因此，這篇論文只探索邊路由這個子問題。 在已知所有點的位置與大小，以及逐一加入與路由新的邊的假設之下，本篇論文實作和比較了數種邊路由的方法。最後，將利用可見性圖找到避開所有點的路徑之方法，衍伸成基於加權式可見性圖的方法，可以同時避開所有點和最小化新路徑的邊交叉數目。 不過這個方法的短處，是它的執行時間主要取決於圖的大小，以致需避開之障礙物很少的邊路由之執行時間，和有許多需避開之障礙物的邊路由之執行時間一樣久。這篇論文介紹一個新方案來改善這個短處。新方案的執行時間主要取決於路由的邊需避開之障礙物的數量，而能顯著地減少一般情況的執行時間。A solution to the problem of graph drawing can be considered to have two components, which are the positions of vertices and the routes of edges. These two components are not independent, and both need to be considered in order to produce a drawing that is more readable. However, the complexity of this problem, even a simpler version that only minimizes edge crossings, is already known to be NP-complete [1]. Thus, this thesis seeks to explore only the sub-problem of edge routing. With the assumptions of knowing the positions and sizes of vertices and routing new edges one by one, this thesis implements and compares several methods of edge routing. Eventually, a visibility graph based method that can find routes which avoid vertices is extended to a weighted visibility graph based method that can not only avoid vertices but also minimize the number of edge crossings of the new route. However, a shortcoming of this method is that its execution time depends primarily on the size of the graph such that routing an edge that needs to avoid few obstacles takes nearly as much time as routing an edge that needs to avoid many obstacles. This thesis improves on this by introducing a new approach whose execution time depends primarily on the number of obstacles that the edge being routed must avoid and is able to significantly reduce execution time for average cases.969766 bytesapplication/pdfen-US邊路由邊交叉最小化最短路徑加權式可見性圖重複擴張子圖edge routingedge crossings minimizationshortest pathweighted visibility graphrepeatedly expanding subgraphthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/254115/1/ntu-101-R99921041-1.pdf