具骨架的超圖繪製

Abstract

此篇論文主要在探討超圖繪製在每條超邊都有連接著一條骨架的情況下，三種美觀標準的最佳化。而三種美觀標準分別為交叉數的最小化、超邊總長度的最小化、以及在超邊互不重疊的情況下，最大數目的超邊放置量。在交叉數的最小化方面，如果有一定的順序，則可以用動態規劃演算法求解。在超邊總長度最小化方面，可以將問題轉換成 bipartite matching 去求解。另外，在超邊放置最大量方面，則用貪婪法求解。此篇論文在骨架類型方面，包含有僅有水平骨架的超圖類型、同時有水平與垂直骨架的超圖類型，以及同時有水平、垂直、斜45度角水平骨架的超圖類型。

The thesis mainly discusses various optimization problems with respect to three aesthetic criteria in hypergraph drawings under the condition that each hyperedge has one backbone. The aesthetic criteria include minimizing the number of crossings, the total hyperedge length, and maximizing the number of hyperedges under the condition that a hypergraph has no overlapping hyperedge. In the aspect of crossings minimization, if there is an order among the hyperedges, we can use a dynamic programming algorithm to solve it. In the aspect of total length minimization, we transform the problem into the bipartite matching problem to solve it. In the aspect of maximizing the number of hyperedges, a greedy algorithm is proposed. Also, the thesis considers three different types of backbones: with horizontal backbones only, with both horizontal and vertical backbones, and allowing horizontal, vertical and octilinear horizontal backbones.