「最小化交叉點問題」是指將網路節點配置在平面上，試著去找出一個較佳的配置方式，使得網路連線與連線之間產生的交叉點最少。在許多的應用中，例如Circuit Board Layout、VLSI Circuit Layout、Automated Graph Drawing等，「最小化交叉點問題」一直是相當重要的一環，愈低的交叉點數量，往往代表著愈低的成本。在這篇論文中，我們研究的題目比「最小化交叉點問題」更特定，我們僅討論FLCNP（Fixed Linear Crossing Number Problem）。FLCNP類似k-pages book crossing number中的兩頁交叉點問題，指將所有的節點排成一條直線，我們稱之為「節點線」，由節點線所區隔開的上下兩個區域我們稱之為「頁面」。節點與節點在連接時，該連線必須以弧線的方式在上下兩個頁面做連接，連線不可從任一邊的頁面跨越節點線到另一邊的頁面。另外還需符合兩個條件，一是節點為有順序性而且是預先就知道的；二是節點的位置是固定不可變動的。我們藉由實作幾個現有的演算法，分析其優缺點，進而提出利用回顧調整的方式來有效降低交叉點的數量

This thesis studies the problem of crossing number reduction in drawing a graph on a two dimensional plane. Crossing number reduction problem is an important part among many applications, such as circuit board layout, VLSI circuit layout and automated graph drawing and so on. For those applications, lower crossing number means lower cost. This thesis focus on the reduction of crossing number in FLCNP (Fixed Linear Crossing Number Problem). The problem of fixed linear crossing number is to arrange all network nodes along a “node line” according to a pre-arranged order. Each edge is drawn as a semicircle above or below the node line. Existing heuristic algorithm of crossing reduction are analyzed and a “retracing and adjusting edge algorithm” for effective crossing reduction are proposed in this thesis.

目錄
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 2
1.3 相關研究 3
1.3.1 尼可森之經驗法則 3
1.3.2 分支限制演算法 3
1.3.3 最大切割解法 4
1.3.4 Cimikowski的演算法 5
第二章 演算法介紹與實作 7
2.1 交叉點定義 7
2.2 實驗環境 8
2.3 Greedy Algorithm 9
2.3.1 介紹 9
2.3.2 演算法 10
2.3.3 演算法說明 10
2.4 Edge-Length Algorithm 11
2.4.1 介紹 11
2.4.2 演算法 12
2.4.3 演算法說明 12
2.5 Maximal Planar Algorithm 13
2.5.1 介紹 13
2.5.2 演算法 14
2.5.3 演算法說明 15
2.6 One-Page Algorithm 16
2.6.1 介紹 16
2.6.2 演算法 18
2.6.3 演算法說明 19
2.7 Crossing-Probability Algorithm 20
2.7.1 介紹 20
2.7.2 演算法 21
2.7.3 演算法說明 21
2.8 相關Function 22
2.8.1 讀取網路圖 22
2.8.2 新增連線 23
2.8.3 取得交叉點數量 23
2.8.4 傳回任一Edge的內外節點 24
2.9 實驗步驟及分析 25
2.10 各演算法重新配置網路圖後之實驗數據 28
2.10.1 各演算法重新配置隨機網路數據 28
2.10.2 各演算法重新配置小世界網路數據 37
2.11 各演算法特性分析 46
2.11.1 Greedy Algorithm 46
2.11.2 Edge-Length Algorithm 47
2.11.3 Maximal Planar Algorithm 48
2.11.4 One-Page Algorithm 49
2.11.5 Crossing-Probability Algorithm 49
第三章 回顧調整方法 50
3.1 由來 50
3.2 演算法介紹 52
3.3 演算法列表及說明 54
3.4 實驗步驟及結果比較 58
3.4.1 實驗步驟 58
3.4.2 結果比較 58
3.5 回顧調整方法重新配置網路圖後之實驗數據 63
3.5.1 利用回顧調整方法重新配置隨機網路數據 63
3.5.2 利用回顧調整方法重新配置小世界網路數據 81
第四章 結論與展望 99
4.1 結論 99
4.2 未來展望 99
參考文獻 100
附錄－英文論文 101


圖目錄
圖1.1.1　磚塊工廠磚窯與倉庫的鐵軌連接方式 1
圖1.2.1　FLCNP示意圖 2
圖1.3.3.1　對網路圖G的所有連線進行編號 4
圖1.3.3.2　反矩陣圖形G' 5
圖2.1　與連線E{i,j}發生交叉點的條件 7
圖2.3.1　Greedy演算法說明圖 9
圖2.4.1　Edge-length演算法說明圖 11
圖2.5.1　Maximal planar演算法說明圖 13
圖2.6.1　One-page演算法說明圖 17
圖2.7.1　Crossing-Probability演算法說明圖 20
圖2.8.4　內外部節點說明 24
圖2.9.1　隨機網路示意圖 26
圖2.9.2　規則網路示意圖 26
圖2.9.3　小世界網路示意圖 26
圖2.10.1.1　節點數為10之隨機網路經各演算法重新配置後的交叉點曲線圖 29
圖2.10.1.2　節點數為20之隨機網路經各演算法重新配置後的交叉點曲線圖 32
圖2.10.1.3　節點數為30之隨機網路經各演算法重新配置後的交叉點曲線圖 35
圖2.10.2.1　節點數10之小世界網路經各演算法重新配置後之交叉點曲線圖 38
圖2.10.2.2　節點數20之小世界網路經各演算法重新配置後之交叉點曲線圖 41
圖2.10.2.3　節點數30之小世界網路經各演算法重新配置後之交叉點曲線圖 44
圖2.11.2　Edges{i,j} 47
圖2.11.3　節點１與節點２的連線各別分佈在上頁面及下頁面 48
圖2.11.5　Edges{i,j} 49
圖3.1.1　（a）為原始網路圖（b）為最佳配置圖 51
圖3.1.2　Edges{1,4}及Edges{2,5}包住了其它所有的連線 51
圖3.1.3　因節點３連線的頁面選擇不佳，造成大量的交叉點 51
圖3.2.1　回顧調整方法選擇需調整的連線 53
圖3.5.1.1　各演算法使用回顧調整方法後交叉點曲線圖 64
圖3.5.1.2　各演算法使用回顧調整方法後交叉點曲線圖 66
圖3.5.1.3　各演算法使用回顧調整方法後交叉點曲線圖 68
圖3.5.1.4　各演算法使用回顧調整方法後交叉點曲線圖 70
圖3.5.1.5　各演算法使用回顧調整方法後交叉點曲線圖 72
圖3.5.1.6　各演算法使用回顧調整方法後交叉點曲線圖 74
圖3.5.1.7　各演算法使用回顧調整方法後交叉點曲線圖 76
圖3.5.1.8　各演算法使用回顧調整方法後交叉點曲線圖 78
圖3.5.1.9　各演算法使用回顧調整方法後交叉點曲線圖 80
圖3.5.2.1　各演算法使用回顧調整方法後交叉點曲線圖 82
圖3.5.2.2　各演算法使用回顧調整方法後交叉點曲線圖 84
圖3.5.2.3　各演算法使用回顧調整方法後交叉點曲線圖 86
圖3.5.2.4　各演算法使用回顧調整方法後交叉點曲線圖 88
圖3.5.2.5　各演算法使用回顧調整方法後交叉點曲線圖 90
圖3.5.2.6　各演算法使用回顧調整方法後交叉點曲線圖 92
圖3.5.2.7　各演算法使用回顧調整方法後交叉點曲線圖 94
圖3.5.2.8　各演算法使用回顧調整方法後交叉點曲線圖 96
圖3.5.2.9　各演算法使用回顧調整方法後交叉點曲線圖 98


表目錄
表2.10.1.1　節點數為10之隨機網路經各演算法重新配置後的相關數據 29
表2.10.1.2　節點數為20之隨機網路經各演算法重新配置後的相關數據 32
表2.10.1.3　節點數為30之隨機網路經各演算法重新配置後的相關數據 35
表2.10.2.1　節點數為10之小世界網路經各演算法重新配置後的相關數據 38
表2.10.2.2　節點數為20之小世界網路經各演算法重新配置後的相關數據 41
表2.10.2.3　節點數為30之小世界網路經各演算法重新配置後的相關數據 44
表3.4.2.1　節點數為10之隨機網路數據比較 60
表3.4.2.2　節點數為20之隨機網路數據比較 60
表3.4.2.3　節點數為30之隨機網路數據比較 61
表3.4.2.4　節點數為10之小世界網路數據比較 61
表3.4.2.5　節點數為20之小世界網路數據比較 62
表3.4.2.6　節點數為30之小世界網路數據比較 62
表3.5.1.1　各演算法使用回顧調整方法後相關數據 64
表3.5.1.2　各演算法使用回顧調整方法後相關數據 66
表3.5.1.3　各演算法使用回顧調整方法後相關數據 68
表3.5.1.4　各演算法使用回顧調整方法後相關數據 70
表3.5.1.5　各演算法使用回顧調整方法後相關數據 72
表3.5.1.6　各演算法使用回顧調整方法後相關數據 74
表3.5.1.7　各演算法使用回顧調整方法後相關數據 76
表3.5.1.8　各演算法使用回顧調整方法後相關數據 78
表3.5.1.9　各演算法使用回顧調整方法後相關數據 80
表3.5.2.1　各演算法使用回顧調整方法後相關數據 82
表3.5.2.2　各演算法使用回顧調整方法後相關數據 84
表3.5.2.3　各演算法使用回顧調整方法後相關數據 86
表3.5.2.4　各演算法使用回顧調整方法後相關數據 88
表3.5.2.5　各演算法使用回顧調整方法後相關數據 90
表3.5.2.6　各演算法使用回顧調整方法後相關數據 92
表3.5.2.7　各演算法使用回顧調整方法後相關數據 94
表3.5.2.8　各演算法使用回顧調整方法後相關數據 96
表3.5.2.9　各演算法使用回顧調整方法後相關數據 98

[1] D. Bienstock and N. Dean, “New Results on Rectilinear Crossing Numbers and Plane Embeddings,” Journal of Graph Theory, vol. 16, pp. 389-398, 1992.
[2] D. Bienstock and N. Dean, “Bounds for Rectilinear Crossing Numbers,” Journal of Graph Theory, vol. 17, pp. 333-348, 1993.
[3] C. Buchheim and L. Zheng, “Fixed linear crossing minimization by reduction to the maximum cut problem,” Proceedings 12th Computing and Combinatorics Conference vol. 4112/2006, pp. 507-516, 2006.
[4] R. Cimikowski, “Algorithms for the fixed linear crossing number problem,” Discrete Applied Mathematics, vol. 122, pp. 93-115, 2002.
[5] R. Cimikowski, “An analysis of some linear graph layout heuristics,” Journal of Heuristic, vol. 12, pp. 143-153, 2006.
[6] R. Cimikowski and B. Mumey, “Approximating the Fixed Linear Crossing Number,” Discrete Applied Mathematics, vol. 155, pp. 2202-2210, 2007.
[7] F. T. Leighton, “New lower bound techniques for VLSI,” Foundations of Computer Science, 1981. SFCS '81. 22nd Annual Symposium on pp. 1-12, 1981.
[8] S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa, “Crossing minimization in linear embeddings of graphs,” IEEE Transactions on Computers, vol. 39, pp. 124-127, 1990.
[9] T. Nicholson, “Permutation procedure for minimising the number of crossing in a network,” IEE Proceedings, vol. 115, pp. 21-26, 1968.
[10] F. Shahrokhi, O. Sykora, L. Szekely, and I. Vrt’o, “The book crossing number of a graph,” Journal of Graph Theory, vol. 21, pp. 413-424, 1996.
[11] R. Tamassia, G. D. Battista, and C. Batini, “Automatic graph drawing and readability of diagrams,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 18, pp. 61-79, 1988.
[12] R. L. Wang and Z. Tang, “A Parallel Algorithm for Fixed Linear Crossing Number Problem,” International Journal of Computer Science and Network Security, vol. 6, pp. 59-64, 2006.