廣義逃脫繞線問題在基板設計規劃中是很棘手的問題。使用幾何角度的繞線方法已經研究及發展了多年，然而繞線成率依然是無法突破的瓶頸。廣義逃脫繞線問題，例如：由導孔繞線到手指、由凸塊繞線到邊界、由手指繞線到邊界，即便在現代封裝設計中，依然由人力完成。本論文以拓撲的角度解決廣義逃脫繞線問題。相較於使用幾何角度的繞線方法，使用拓撲角度的繞線方法在解決繞線問題的初期專注於繞線的拓撲關係，這有助於避免繞線初期階段決定過多細節，降低計算複雜度。
首先，將環形拓墣表示法的抽象介面建立地完整，我們的研究指出，若要發展基於環形拓墣表示法的繞線演算法，關鍵在於要加入更多資訊到抽象介面，才能得到更好的繞線結果。原論文提出的基本環形拓撲繞線演算法理論上保證拓墣百分百的繞線成功率，但實際應用上產生的結果會有過度纏繞的問題，以至於無法在下個階段轉成幾何繞線。為了解決這個問題，我們提出將嵌入樹林的資訊納入環形拓墣表示法的抽象介面，並使用三鏈結表來說明我們提出的新的環形拓墣表示法的抽象介面以及三鏈結資料結構。接著，我們提出拓撲跳脫繞線演算法，搭配啟發式目標偏差值的最小成本樹林，此搭配可以大幅減少纏繞問題，且可以在幾秒內就得到結果。依據我們的研究結果，我們展示了廣義拓撲繞線問題可在繞線設計規劃初期，以拓撲繞線的角度有效率地解決。

General escape routing problem is a challenging problem in substrate design.
Although geometrical routing methodology has been researched and developed for
years, the routing completion rate has been a bottleneck. In modern package design, the escape routing problems, such as wire connections from vias to finger rows,
from bump-balls to peripheral boundary, and from fingers to escape boundary, can
only be solved by a substantial amount of manual effort. In this work, we tackle
the problem from a topological routing perspective. Compared to geometrical routings, topological routings focus on the topology of paths, which greatly helps to
avoid making unnecessarily detailed decisions in early design planning stage and to
reduce computation complexity. Firstly, we indicate that the circular frame interface should include more information to develop a circular-frame-based algorithm
that generates a quality solution. The basic circular frame routing algorithm theoretically guarantees 100% completion rate. However, the solution may suffer from
path tangling problem and is unrealistic to transform into a homotopic geometrical
sketch. To tackle this issue, we develop the circular frame interface including the
information of the forest style of the embedding frame, and use the triple-lists
table which is a diagram illustrating the circular frame interface and its underlying data structure to represent a topology class. We apply the topology escape
routing algorithm on the minimum spanning forest of heuristic target net
offset, which generates a solution that effectively alleviates the path tangling problem in seconds. Based on the experimental results, we demonstrate that the escape
routing problem could be efficiently and effectively resolved via topological routing
perspective in early design planning stage.

[1] Rak-Kyeong Seong, Chanho Mina, Sang-Hoon Hanr, Jaeho Yanga, Seungwoo
Nama, Kyusam Oha, “Topology and Routing Problems: The Circular Frame,”
arXiv, arXiv:2105.03386, 2021.
[2] Rak-Kyeong Seong, Jaeho Yanga, Sang-Hoon Han, “Topology for Substrate
Routing in Semiconductor Package Design,” arXiv, arXiv:2105.07892, 2021.
[3] Wayne Wei-Ming Dai, Raymond, and Jeffrey Jue, Masao Sato, “Rubber Band
Routing and Dynamic Data Representation,” International Conference on
Computer-Aided Design, 1990.
[4] David Joseph Staepelaere, “Geometric Transformations for a Rubber-band
Sketch,” M. S. thesis, University of California Santa Cruz, 1992.
[5] Tal Dayan Wayne, “Rubber-band Based Topological Router,” M. S. thesis,
University of California Santa Cruz, 1992.
[6] David Staepelaere, Jeffrey Jue, Tal Dayan, WayneDai, “SURF: Rubber-band
Routing System for Multichip Modules,” IEEE Design & Test of Computers,
P.18-26, 1993.
[7] K. Kawamura, T. Shindo, T. Shibuya, H. Miwatari, and others, “Touch and
cross router,” IEEE International Conference on Computer-Aided Design, 1990.
[8] H. Murata, and Y. Kajitani, “Interactive terminal sliding algorithm for hybrid
IC planar layout,” Transactions of Information Processing Society of Japan,
Vol.35, No.23, pp.2806-2815, 1994.