結構化樹狀圖中交錯最小化問題之研究

Abstract

在欄位樹與系統發生網路等結構化的樹狀網路視覺化中，額外的結構限制或非樹狀邊往往使繪圖無法避免交錯，而交錯數的數量直接影響視覺化的可讀性，因此如何有效地最小化交錯數成為此類視覺化繪製中的核心問題。既有研究針對欄位樹提出三種布局變體，並證明其在正交繪圖與特定布局變體下的交錯數最小化問題分別為固定參數可解與 NP-hard；亦有研究針對系統發生網路提出耳狀、蛇形、水平三種繪圖風格，並證明耳狀繪圖可於多項式時間內求解，另兩者則分別為固定參數可解與 NP-complete。 本論文以此為基礎，從複雜度分析與演算法設計兩個面向擴展既有結果。複雜度分析方面，我們針對正交輻射式繪圖下的欄位樹，證明在固定欄位順序時，無序二元樹的交錯數最小化問題為 NP-hard ，並給出以跨欄邊數量為參數的固定參數演算法；當改為允許欄位順序可變的有序二元樹時，問題轉為 NP-complete，而若樹的順序與欄位順序皆固定，問題則退化為可直接求解。在系統發生網路方面，我們提出耳狀繪圖的放寬限制變體，證明放寬冗餘邊方向限制後，交錯數最小化問題會變為 NP-hard。演算法設計方面，針對欄位樹交錯數最小化問題在較寬鬆布局變體下仍屬 NP-hard 的情形，我們建立一個分解引理，證明總交錯數可拆解為僅與欄位順序相關的外層項，以及與欄內子樹排列相關的內層項，此問題亦可引導至特定條件的整數規劃問題。最後，我們以真實的生命之樹（Tree of Life）親緣關係資料為基礎，透過 Tabu Search 對內層子問題進行實驗評估，結果顯示該方法較隨機排列能大幅降低交錯數，並在可驗證的小型案例中達到已知最佳解，但同時也顯示計算時間隨子樹數量增加而快速上升，反映出此問題目前仍缺乏多項式時間演算法。

In tree-based network visualizations such as column trees and phylogenetic networks, additional structural constraints or non-tree edges often make edge crossings unavoidable, and the number of crossings directly affects the readability of the visualization. Effectively minimizing the number of crossings is therefore a central problem in drawing such structures. Prior work has proposed three layout variants for column trees and shown that, under orthogonal drawings, the crossing minimization problem is, depending on the variant, either fixed-parameter tractable or NP-hard. Other work has proposed three drawing styles for phylogenetic networks: horizontal, snake, and ear. The work also showed that the ear style admits a polynomial-time algorithm, while the snake style is fixed-parameter tractable and the horizontal style is NP-complete.

Building on the attribution, this thesis extends existing results along two directions: complexity analysis and algorithm design. For complexity analysis, we consider column trees under ortho-radial drawings and prove that, when the column order is fixed, the crossing minimization problem for unordered binary trees is NP-hard, and we give a fixed-parameter algorithm parameterized by the number of inter-edges. When the column order is not fixed, the problem becomes NP-complete. When both the tree order and the column order are fixed, the problem becomes trivial to solve. For phylogenetic networks, we introduce a relaxed variant of the ear-style drawing and show that relaxing the routing-direction constraint on reticulation edges makes the crossing minimization problem NP-hard. For algorithm design, since the crossing minimization problem for column trees remains NP-hard under more flexible layout variants, we establish a decomposition lemma showing that the total number of crossings can be split into an outer term, which depends only on the column order, and an inner term, which depends on the arrangement of subtrees within each column; this problem can further be formulated as an integer programming problem under specific conditions. Finally, using real phylogenetic data from the Tree of Life dataset, we evaluate the inner subproblem experimentally with the Tabu Search heuristic. The results show that this method substantially reduces the number of crossings compared to random orderings and reaches the known optimal solution in small, verifiable cases; at the same time, the running time increases rapidly as the number of subtrees grows, indicating that no polynomial-time algorithm is currently known for this problem.