摘要
圖(graph)是個常見的數學模型，能描述各種複雜的科學和工程問題。圖形繪製(Graph drawing)是將一個圖表示在二維或三維空間的過程，讓圖的結構以易於理解的方式呈現出來。由於這議題的重要性，圖形繪製已成為計算機科學中一個快速成長的新興領域。 在眾多圖形繪製的問題中，圖的接觸表示法(contact representations of graphs)在近年來受到的關注不斷提升。給定一個圖，它的接觸表示法即是將圖中的各個節點對應到二維或三維空間的幾何物件，其中任兩個節點在圖上相鄰若且唯若他們對應的物件互相接觸。 在許多接觸表示法中， rectilinear dual 是一個經典的繪製風格，能應用於大型積體電路的布圖規劃。在該繪製風格中，圖中的各個節點用正交多邊形來表示，多邊形的相鄰對應於節點在圖中的相鄰關係，並且所有的多邊形合起來恰好成為一個長方形。 在本論文的前半，我們探討如何在多邊形形狀被限制的情形下設計 rectilinear dual。因凸形(convex shapes) 傾向比非凸形來得好看且單純，我們提出並探討一個新的圖形繪製風格 - orthogonally convex drawing，研究如何設計 rectilinear dual 的演算法使得其中的幾何物件皆為正交凸多邊形(orthogonally convex polygons)。 另外，為了瞭解各形狀在繪製 rectilinear dual 中的功用與限制，我們探討可用形狀被限制下的rectilinear dual。 我們算出 T-free rectilinear dual 的多邊形複雜度，驗證了 T 形是最有用的八邊形之直覺。 在本論文的後半，我們探討如何將 rectilinear dual 延伸及推廣到二維正交以外的情境上。為了容納凸多邊形(convex polygons)，我們提出並探討一個新的圖形繪製風格 - convex polygonal dual。 針對這項繪製風格，我們提出一些新的技術及fixed-parameter tractability 的結果。為了容納正交多面體(orthogonal polyhedra)，我們提出並探討一個新的圖形繪製風格 - 3D floorplan。我們證明了所有 chordal graph 都能畫成 3D-floorplan。 我們的畫法不但只需用到兩層，也能夠實現任意對其中多面體指定的體積。 總體來說，在圖的接觸表示法之框架下，本論文提供了許多新的技術及觀點。希望這篇論文指引出的研究方向能讓我們對這個充滿挑戰性的領域有更全面的認識。
並列摘要
Graph represents one of the most popular abstract models in describing complex science and engineering problems. Graph drawing refers to the process of displaying an abstract graph in 2D or 3D, allowing the structure as well as the meaning of the graph to be understood better and easier. As a consequence, the design of graph drawing algorithms has become an emerging and fast growing research area in computer science. Among problems of interest in the graph drawing community, the topic of contact representations of graphs has received increasing attention over the years. Given a graph, a contact representation of the graph is to map each vertex of the graph to a geometric object in 2D or 3D so that two vertices are adjacent iff their corresponding objects "touch". A rectilinear dual, a classic drawing style which has found applications in VLSI floor-planning, requires that each vertex be drawn as a rectilinear polygon, adjacency in a graph correspond to side-contact in the drawing, and all rectilinear polygons together form a partition of a rectangle. In the first half of the thesis, we investigate a variety of shape constraints in rectilinear duals. As convex objects tend to be visually more pleasing, the drawing style orthogonally convex drawing is proposed and investigated. In addition, we study rectilinear duals using a restricted set of shapes, in order to understand the power and the limitation of different shapes in rectilinear duals. We determine the optimal polygonal complexity of T-free rectilinear dual, justifying the intuition that T-shape is the most useful 8-sided polygon. In the second half of the thesis, we study possible extensions and generalizations of rectilinear duals beyond the 2D rectilinear setting. To accommodate convex polygons, the drawing style convex polygonal dual is proposed and investigated. We demonstrate several new techniques and fixed-parameter tractability results to deal with this drawing style. We also propose and investigate a new drawing style called 3D floorplan, using rectilinear polyhedra as building blocks. We show that every chordal graph admits a 3D-floorplan which uses only two layers and is also capable of realizing any volume-assignment to its constituent polyhedra. In summary, the thesis provides a variety of new techniques and new perspectives within the framework of contact representations of graphs. We hope that this study could lead to a better understanding of contact graph representations - an exciting and challenging topic in graph drawing.
參考文獻
[1] Nieke Aerts. Geometric Representations of Planar Graphs. PhD thesis, Technischen Universität Berlin, 2015.
[3] Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, and Stephen G. Kobourov. Linear-time algorithms for hole-free rectilinear proportional contact graph representations. Algorithmica, 67(1):3--22, 2013.
[6] Giuseppe Di Battista, Giuseppe Liotta, and Francesco Vargiu. Spirality and optimal orthogonal drawings. SIAM Journal on Computing, 27(6):1764--1811, 1998.
[10] Yi-Jun Chang and Hsu-Chun Yen. Rectilinear duals using monotone staircase polygons. In Zhao Zhang, Lidong Wu, Wen Xu, and Ding-Zhu Du, editors, Combinatorial Optimization and Applications, volume 8881 of Lecture Notes in Computer Science, pages 86--100. Springer International Publishing, 2014.
[13] Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12--75, 1990.