Visibility Representation with Congruent Segments on Planar Graphs

平面圖的等線段可視性表示圖之研究

陳聿揚(Yu-Yang Chen)

指導教授 ： 潘雙洪

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

https://doi.org/10.6843/NTHU.2012.00677

摘要

近年來，在計算幾何與圖形理論中，圖形繪製是一個經常深受探討的問題。圖形繪製根據不同的表示原則發展出相當多種不同的表示法，舉例來說，有直線繪圖與正交線繪圖等。在此篇論文中，我們專注在其中一種關於平面圖的重要表示法，可視性表示圖。
平面圖的可視性表示圖就是將平面圖上的點以不交錯的水平線段呈現，而當平面圖的某兩點相連時，其相連之邊在可視性表示圖中以垂直線段呈現，並與兩條表示相對應兩點的水平線段相連。針對平面圖的可視性表示圖，我們證明求一個平面圖的最小面積的可視性表示圖是一個NP-complete複雜度的問題。
等線段可視性表示圖是可視性表示圖的一種變形，它符合可視性表示圖的所有特性，且增加一個條件，平面圖的所有點以不交錯的等長水平線段呈現。我們證明判斷一個平面圖是否擁有等線段可視性表示圖是一個NP-complete複雜度的問題。我們也證明了判斷一個平面圖是否擁有指定長度的等線段可視性表示圖是一個NP-complete複雜度的問題。
另一方面，我們設計了兩個求特定圖形上的等線段可視性表示圖之演算法，首先，我們提出一個在O(n)時間內得到關於outerplanar graphs的等線段可視性表示圖之演算法。接著，我們提出一個演算法可在O(n)時間內得到關於bipartite planar graphs的等線段可視性表示圖。

關鍵字

圖形繪製 ； 可視性表示圖

並列摘要

In recent years, graph drawing plays an important role in computational geometry and graph theory. There are many different ways to represent graphs, for example, straight line drawing and orthogonal drawing. In our thesis, we focus on the visibility representation (or VR for short) of planar graphs. Let G be a plane graph with n vertices. In a visibility representation of G, each vertex of G is represented as a horizontal line segment (called vertex segment), and two vertex segments are connected by a vertical line segment (called edge segment) if the corresponding vertices are adjacent in G.
Rosenstiehl and Tarjan conjectured that minimizing the area of visibility representation is NP-hard. In this thesis, we reduce from 3SAT problem and show the area-minimization problem of visibility representation is NP-complete.
A visibility representation with congruent segments (or VRCS for short) is a variant of visibility representation, which is similar to VR, but all vertices of G are represented as equal length horizontal line segments. We show that the VRCS drawing problem for general planar graphs is NP-complete. We also prove the problem of visibility representation with congruent segments of fixed length (or VRCSFL for short) on planar graphs is NP-complete.
Apart from NP-hardness proofs, we provide a VRCS drawing algorithm for outerplane graphs in O(n) time, and an O(n) time VRCS drawing algorithm for bipartite plane graphs, respectively.

並列關鍵字

Graph drawing ； Visibility representation

參考文獻

[23] R.H.J.M Otten and J.G. van Wijk, Graph representations in interactive layout design, Pro-

[1] A. Lempel, S. Even and I. Cederbaum, An algorithm for planarity testing of graphs, Theory

of Graphs, 1967.

[2] C.C. Lin , H. I. Lu and I.F. Sun, Improved compact visibility representation of planar graph

[3] C.Y. Chen, Y.F. Hung and H.I. LU Visibility representations of four-connected plane graphs