用單位正方形為節點及少量彎曲的邊之正交圖形畫法

Orthogonal Drawing with Vertices as Unit Squares and Few Bends per Edge

林昱安(Yu-An Lin)

指導教授 ： 潘雙洪

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

摘要

近年來，圖形繪製為一個經常受探討的議題。尤其是以正交畫法受到注目，其只用到垂直與水平線段來做圖形的畫法，因此容易讓人辨識圖形的樣貌。在平面及非平面的圖形上，都有研究其正交畫法。在此，我們只針對非平面圖做討論。正交畫法中所討論的議題有許多，像是減少每條邊上所需的彎曲數量，減少圖中總共所需的彎曲數，減少邊之間的交叉數量，等等。在過去的研究中，圖形中節點的形狀，往往會根據其維度的變化，而有所改變。此外，節點上每邊之間的距離，也會因為維度過高，而有所減少。因此，為了針對節點能有固定大小，而且每邊之間也有固定的距離。我們提供了一個演算法，將每個節點放在格網上，並且以對角線的方向來做擺放。同時，線段則是畫在格線上，用以清楚區別每條線段。使得圖形能夠兼顧，節點形狀以及每邊之間有清晰的呈現。在此方式下，我們的目標在於，求得每邊最多所需要用到的彎曲數量，以及整個圖形最多所需要使用到的面積。所得到的結論為，在圖形中節點維度不超過6以上，每邊能以最多2次彎曲畫出；節點維度不超過8以上，每邊能以最多3次彎曲畫出。面積則是限制在O(n2) 的大小。此外，針對圖形是否能夠，以每邊皆無彎曲的方式下畫出，我們證明其為一個NPC的問題。

關鍵字

圖形繪製 ； 正交圖形畫法 ； 彎曲數目 ； NPC問題

並列摘要

Every 4-graph has an orthogonal drawing with vertices drawn as grid points, where a k-graph is a graph of maximum vertex degree k. However, any plane k-graph with k 5 does not have an orthogonal grid drawing. Note that in our drawing, edge crossings are allowed, but edge
overlapping is not allowed. In order to draw graphs of arbitrarily high vertex degree, other objects
like rectangles have been used to represent the vertices of the graph. However, rectangular shapes
could be fat or skinny, and hence irregular. This motivates us to investigate the representation of
vertices by consistent unit grid squares (instead of general rectangles).

Our consideration is that with consistent shapes for all vertices, the drawn graphs have the
advantage of great clarity for visualization purposes. With such a kind of representation, 8-graphs
can now be drawn, and thus we broaden the classes of graphs that we can draw to quite some
extent.

Our objective is to find a drawing with few bends per edge. We present quadratic-time algorithms
to construct the orthogonal grid drawing of 5-graphs and 6-graphs such that each edge
contains at most two bends, and to construct the orthogonal grid drawing of 8-graphs such that
each edge contains at most three bends. Moreover, we show that the decision problem of determining
whether an 8-graph has an orthogonal grid drawing without edge-bends is NP-complete. The
last result implies that the problem to minimize the number of bends on edges in the orthogonal
drawing under the model where vertices are represented as unit grid squares or even as general
rectangles is thus NP-complete.

並列關鍵字

Graph Drawing ； Orthogonal Graph Drawing ； Number of bends ； NPC problem

參考文獻

[1] C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity-relationship diagrams.

[2] C. Batini, E. Nardelli, and R. Tamassia. A layout algorithm for data-flow diagrams. IEEE

Trans. on Software Engineering, SE-12(4), pp. 538-546, 1986.

[3] S. Bridgeman et al. An algorithm for interactive orthogonal graph drawing. In Proc. of GD

[4] U. Brandes and D. Wagner. Dynamic grid embedding with few bends and changes. In Proc.