「最小化交叉點問題」是指將網路節點配置在平面上，試著去找出一個較佳的配置方式，使得網路連線與連線之間產生的交叉點最少。在許多的應用中，例如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.
