平面圖繪制算法的研究與實現(xiàn)

王銀媛

（武進開放大學， 江蘇 常州 213149）

平面圖繪制算法的研究與實現(xiàn)

王銀媛

（武進開放大學， 江蘇 常州 213149）

圍繞平面圖繪制的“平面圖節(jié)點繪制順序和平面圖節(jié)點坐標確定”兩個問題進行研究，重點闡述了平面圖節(jié)點繪制順序的兩種方法(規(guī)范次序法和規(guī)范分解法)，并在此基礎(chǔ)上研究了畫法的具體算法，并對應用性進行了探究。

平面圖；規(guī)范次序；規(guī)范分解；平面圖直線畫法；平面圖凸形畫法

平面圖繪制算法的研究與實數(shù)據(jù)可視化技術(shù)是當前計算機研究的熱點之一，用各種各樣的圖形表示數(shù)據(jù)，可以更直觀地顯示數(shù)據(jù)的本質(zhì)。若能通過對平面圖繪制算法的研究與開發(fā)，并使其應用于可視化技術(shù)平臺開發(fā)，對數(shù)據(jù)的表示將具有十分重要的應用價值。

圖是一種應用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它可以直觀、準確地表示多種復雜的系統(tǒng)模型，其中用圖的頂點表示系統(tǒng)中的元素，圖的邊表示元素之間的關(guān)系。將一個圖美觀、整齊地畫到二維或三維空間的一個有限區(qū)域中具有重要的理論意義和實際應用價值。圖在信息可視化、圖形用戶接口、軟件工程、VLSI布局、電路布線、網(wǎng)絡管理等都有廣泛的應用。一般可將圖結(jié)構(gòu)分為樹、平面圖、一般無向圖、一般有向圖。對于各類圖的結(jié)構(gòu)已有不少畫圖算法，平面圖繪制算法是其中一類重要的算法，許多學者對此作過較為深入的研究?，F(xiàn)有的關(guān)于平面圖的算法都比較復雜，難以理解。尋找簡單，高效的平面圖畫圖算法是一個急需要解決的問題。目前可視化數(shù)據(jù)挖掘的應用可越來越廣泛，也需要各種圖形技術(shù)的支撐。

平面圖是最常用的一種圖，也是在圖論中最清晰明了的表示方法之一，一個理論上可用平面表示的圖，必須要用一定的算法才能將這個圖以平面形式畫出。

一、平面圖繪制的美學標準

根據(jù)應用的不同，對平面圖的繪制也有不同的要求。但在畫平面圖時通常要考慮一定的美觀度。在繪制平面圖時，常用的美學準則如下：

關(guān)聯(lián)于同一頂點的邊所構(gòu)成的最小角最大化；縱橫比不要太大或太??；盡可能使邊長一致；在所畫出的圖中，任意兩個頂點之間的距離不小于規(guī)定的最小值的前提下使圖中所有邊的長度之和最??；在所畫出的圖中，任意兩個頂點之間的距離不小于規(guī)定的最小值的前提下使圖的面積最??；反映圖的內(nèi)在對稱性。

二、平面圖的定義及繪制

（一）平面圖的定義

平面圖是指一個圖能夠在兩維空間中表示，且畫出后，邊與邊沒有交叉[1]。

定義1（平面圖）一個圖如果能在一個平面上畫出，沒有邊交叉，稱為平面圖。

定義2（平面圖的面）平面圖的一個面（face）是以任意拓撲方式用邊圍繞的連接區(qū)域。平面圖中一個無界的面稱為外部面（outface或exterior face）。所有其它的面稱為內(nèi)部面（interior face）。屬于外部面的邊稱為外部邊（exterior edge），屬于外部面的節(jié)點稱為外部節(jié)點（exterior node）。連接兩個外部節(jié)點的邊稱為弦（chord）。

定義3（平面表示）一個圖的平面表示是中節(jié)點對平面中點的映射，中的邊對Jordan曲線的映射。

定義4（平面嵌入）如果圖能畫在一個平面上，并且在中除了端點以外。任意兩條邊都不相交，這樣的畫法所得的圖稱為圖一個平面嵌入。如果可嵌入平面，稱為平面圖，否則稱為非平面圖。

定義5（外平面圖）一個圖，如果所有點都能以出現(xiàn)在外部面上的方式畫出，這個圖稱為外平面圖。

（二）平面圖繪制

平面圖繪制就是將一個理論上可用平面表示的圖，用一定的算法將圖以平面形式畫出。如圖1所示。圖1（a）是一個電路的設計圖，當制作印刷電路板時需要一個平面圖表示，如圖1（b）所示。

圖1平面圖

一般來說，平面圖表示有三個問題要解決：平面圖的平面性問題，平面圖節(jié)點繪制順序問題和平面圖節(jié)點坐標確定問題。平面圖的平面性問題不在本文討論。本文中繪制的圖都是可平面的。平面圖節(jié)點繪制順序決定了一個平面圖是否能正確地畫出，常用的方法有規(guī)范次序法和規(guī)范分解法等方法[2]。

三、基于規(guī)范次序的平面圖繪制

繪制平面圖一般采用節(jié)點添加法。所謂節(jié)點添加法就是在平面圖繪制過程中，逐個增加圖的節(jié)點及相關(guān)的連接邊，直至添加完全部節(jié)點，將平面圖繪制完成。然而，在節(jié)點添加法中，節(jié)點添加的次序是至關(guān)重要的。如果隨意添加節(jié)點，很可能不能得到圖的平面繪制，規(guī)范次序就是一種節(jié)點添加的次序，下面主要討論三角圖的繪制方法。

（一）規(guī)范次序定義

令G是一個畫在平面上的極大平面圖，令u,v,w是其外部面上的邊界。規(guī)范次序是對圖G節(jié)點v1，v2，…，vn的一個標注，也是一種排序，使得v1=u1,v2=v且vn=w。并對3≤k≤n，以下條件成立：

由節(jié)點v1，v2，…，vk-1導出的G的子圖Gk-1是二連通的，且其外部面的邊界是一個環(huán)Gk-1，包含邊(u,v)；

節(jié)點vk在Gk-1的外部面上，在Gk-1中至少有兩個鄰接節(jié)點。并且，vk在Gk-1上的所有鄰接節(jié)點在路徑Gk-1-(u,v)上是連續(xù)的[3]。

規(guī)范次序的說明見圖2。圖是一個極大平面圖，實際上，它也是一個三角圖。節(jié)點，有時稱為一個平面圖的底邊。根據(jù)規(guī)范次序繪制平面圖的基本思想是首先取規(guī)范次序中前兩個節(jié)點作為平面圖的底邊，然后添加節(jié)點，并添加其連接邊，構(gòu)成一個三角形。在此基礎(chǔ)上，逐個添加節(jié)點及其連接邊，直至將圖中的所有節(jié)點都添加到畫面上，完成整個平面圖的繪制。在整個平面圖的繪制過程中，需要不斷調(diào)整圖中節(jié)點的坐標，使其不出現(xiàn)邊的交叉和重疊，保持其平面性。

圖2 規(guī)范次序的說明

規(guī)范次序并不確定節(jié)點的坐標，它只是保證以這樣的次序添加節(jié)點，在繪制過程中能保證平面圖的平面性[4]。

（二）規(guī)范次序算法

規(guī)范次序是在繪制平面圖時，逐個增加節(jié)點的次序。在選擇加入規(guī)范次序的節(jié)點時，需要考慮候選節(jié)點與當前子圖外部面上環(huán)的節(jié)點之間的鄰接關(guān)系[5]。

用反向推理，假定在圖中，已經(jīng)適當?shù)剡x擇了節(jié)點vn，vn-1，…，vk+1（k+1≥4），使得對于滿足規(guī)范次序的條件。如果在環(huán)上能選擇一個節(jié)點作為，不是上一根弦的端點，如圖2.1所示。那么，因為，顯然，滿足規(guī)范次序的條件。因此，存在一個節(jié)點滿足規(guī)范次序的條件。令環(huán)Ck=w1，w2，…，，wt，其中w1=v1，wt=v2。如果Ck沒有弦，那么節(jié)點w2，w3,…，wt-1中的任意節(jié)點就是這樣的節(jié)點w。

圖2.1 規(guī)范次序算法的候選節(jié)點（1）

假定Ck有弦，那么Gk有一個“最小的弦”（wp，wq）(p+2≥q)，使得沒有一個節(jié)點是這根弦的端點，如圖2.2所示（弦用粗線畫出），那么。節(jié)點中的任意節(jié)點都可以作為候選節(jié)點。

圖2.2 規(guī)范次序算法的候選節(jié)點（2）

由上述分析，我們已得到了構(gòu)造規(guī)范次序節(jié)點表的方法。先取3個相鄰接的節(jié)點，這3個節(jié)點能構(gòu)成一個三角形。設這3個節(jié)點能構(gòu)成一個三角形。設這3個節(jié)點為v1,v2,vn，以此為基礎(chǔ)，計算規(guī)范次序節(jié)點表中節(jié)點的規(guī)范次序。

因此，計算三角圖規(guī)范次序算法的數(shù)據(jù)結(jié)構(gòu)如下：

給定三角圖G=(V,E)。對各個節(jié)點v∈V，分配下列屬性：

v.mark，如果v已增加到次序表中為true，否則為falss；

v.out，如果v是當前平面圖的外部節(jié)點為true，否則為flase；

v.chords，端點為v的外部環(huán)的弦個數(shù)。

用c表示子圖Gk-1外部面的環(huán)Ck-1。

四、基于規(guī)范分解的平面圖繪制

當一個平面圖不是三角圖時，規(guī)范次序的要求將更加嚴格。在三角圖中，規(guī)范次序要求vk+1在路徑Ck-(v1，v2)（輪廓）上有連續(xù)的鄰接節(jié)點。然而，考慮圖3.1，G3的外部面是v1，v2，y在這種情況中，如果規(guī)范次序指定v4=x，x的鄰接節(jié)點在C3=v1，y,v2上不形成連續(xù)的片段。因為y不是x的鄰接節(jié)點[6]。

圖3.1 非三角圖

再如圖3.2，添加節(jié)點時，不能構(gòu)成外部面的環(huán)，按上一章的方法，也無法進行平面圖的繪制。

圖3.2 非三角圖的節(jié)點添加

這是因為圖3.1和圖3.2中的圖不是三角圖，需要我們對節(jié)點添加次序有一個新的定義，使我們在繪制圖時，能順利地添加圖中所有節(jié)點。通過節(jié)點添加次序的另一種方法：規(guī)范分解法，可以將平面圖的節(jié)點進行劃分，劃分為單個節(jié)點或多個節(jié)點的子集。在繪制平面圖時，按照劃分的節(jié)點集合進行節(jié)點添加。

（一）連通圖的規(guī)范分解

如果圖G=(V，E)存在兩個節(jié)點x和y，這兩個節(jié)點能把圖G分離為兩個圖G1和G2，稱這一對節(jié)點{x,y}為一個分離對。G1和G2稱為分離圖[7]。

如圖3.3所示，將G1定義為由獲得的分離圖，在G1中，如果沒有邊(x,y)，增加邊(x,y)；將G2定義為由獲得的分離圖，在G2中，如果沒有邊{x,y}，增加邊{x,y}。

圖3.3 分離對和分離圖

圖3.4 不是內(nèi)部3-連通的2-連通平面圖

如果平面圖是2-連通的，對圖的任意分離對，和是外部節(jié)點，并與包含一個外部節(jié)點的相連接，這個平面圖稱為是內(nèi)部3-連通的。

換言之，如果圖是內(nèi)部3-連通的，當且僅當在外部面上增加一個節(jié)點能夠擴展為一個3-連通圖，增加的節(jié)點與所有外部節(jié)點連接。如果一個2-連通圖不是內(nèi)部3-連通的，那么圖中有如圖3.4中所示三種類型的分離對之一。在圖3.4中，分離部分包含一個不是或的外部節(jié)點。

如果一個內(nèi)部3-連通的平面圖不是3-連通的，那么圖有一個外部節(jié)點的分離對，當圖不是一個單獨的環(huán)時，有一個“弦路徑”。

（二）規(guī)范分解算法

在算法中主要是維持一個數(shù)據(jù)結(jié)構(gòu)，在構(gòu)造時，這個數(shù)據(jù)結(jié)構(gòu)保持了的外部鏈和最小弦路徑。下面描述算法的輪廓[8]。

令Gl=G，Gl-1=G-{vn}=G-Ul。在圖G中先找一個度數(shù)大于或等于3的節(jié)點vn，作為單個節(jié)點集合Ul。令Gl-1=Gk，Gl-2=Gk-1，Gk-Uk=Gk-1。算法從G1=Gk開始，找到規(guī)范劃分中的子集Uk，Uk-1,直到找到U1。

從Gl=G起，每找到一個劃分的子集Uk時，將其從當前節(jié)點集合Vk刪除，加入中，得到從Vk-1導出的子圖Gk-1。顯然，與鄰接的節(jié)點都在子圖Gk-1的外部面上。令w1，w2，…，wt是子圖Gk-1的外部節(jié)點，以順時針順序出現(xiàn)在Ck-1上，其中w1=vt和wt=v2。

如果Gk-1是3-連通的。設節(jié)點w是Gk-1中的鄰接節(jié)點，利用規(guī)范分解中的條件（CD3），如果w在Gk-1上是3-連通的，即內(nèi)部3-連通的，Uk-1是單個節(jié)點集合{w}。

如果Gk-1是內(nèi)部3-連通的，且不是3-連通的。則對Ck-1有一個弦路徑。令p是一個對Ck-1的最小弦路徑，令wp和wq是p的兩個端點（p＜q），因為Gk-1是內(nèi)部3-連通的，{wp，wq}是Gk-1的一個分離對，那么q≥p+2。{wp+1，wq+2，…，wq-1}是Gk-1的一個外部鏈。選擇{wp+1，wq+2，…，wq-1}作為Uk-1。因為Uk-1是一個外部鏈，p是一個最小弦路徑，可知Uk-1∩U1≠?。因為G是3-連通的，各個節(jié)點w∈Uk-1在Gk-1中度數(shù)為2，各個節(jié)點w∈Uk-1在中有一個鄰居。實現(xiàn)時，在Gk-1上找內(nèi)部2-連通的節(jié)點w，然后在Gk-1的外部面上找w的鄰接節(jié)點，如u，如果u在Gk-1上是內(nèi)部2-連通的，擴展集合Uk-1，此時Uk-1是Gk-1上的一個外部鏈，如此，直到外部鏈不能再擴展，得到集合Uk-1。

算法的終止條件是，所剩節(jié)點都是內(nèi)部2-連通的，得到U1。因為在構(gòu)造劃分子集Uk時，不斷在原節(jié)點集合V上刪除節(jié)點，加入到中，至多在只有3個節(jié)點時，構(gòu)成一個三角形，此時，這3個節(jié)點都是2-連通的，得到U1，算法得以終止。如果多于3個節(jié)點，這些節(jié)點都是2-連通的，形成一個環(huán)，得到U1，算法得以終止。所以算法一定是可終止的。

規(guī)范分解算法的數(shù)據(jù)結(jié)構(gòu)：

規(guī)范劃分表：，U1,…，U2，U1,其中Ui,為該劃分的節(jié)點集合，各個Ui用一個數(shù)組表示；

在圖G的節(jié)點鄰接矩陣中，開始時鄰接邊用1表示，在劃分過程中，與中節(jié)點鄰接的邊用-1表示。

五、平面圖繪制在平臺上的實現(xiàn)

因考慮到目前的應用基本上都是使用B/S方式，因此使用了WPF技術(shù)，開發(fā)平臺選用Microsoft的.NET平臺。WPF是基于技術(shù).NET的新一代開發(fā)平臺，實現(xiàn)了桌面應用程序和互聯(lián)網(wǎng)應用程序的統(tǒng)一編程，實現(xiàn)了數(shù)據(jù)驅(qū)動用戶界面，編程語言采用C#語言。

在數(shù)據(jù)分析部分，按照數(shù)據(jù)實體和實體之間的關(guān)系確定圖的節(jié)點和邊，構(gòu)造數(shù)據(jù)實體關(guān)系表。在數(shù)據(jù)實體關(guān)系表中，有數(shù)據(jù)實體的各種屬性，與應用密切相關(guān)。在圖形表示程序中，只需要數(shù)據(jù)實體的關(guān)系，因此，利用數(shù)據(jù)實體關(guān)系表中的關(guān)系信息，構(gòu)造一個圖結(jié)構(gòu)，即用圖中的節(jié)點表示現(xiàn)實世界的實體，用圖的邊表示實體之間的關(guān)系。圖結(jié)構(gòu)由兩部分組成：源節(jié)點表和節(jié)點鄰接矩陣。源節(jié)點表包括與數(shù)據(jù)實體關(guān)系表對應的節(jié)點序號，以及顯示的標注信息。節(jié)點鄰接矩陣用圖的關(guān)聯(lián)邊表示實體之間的關(guān)系，這樣就能做到數(shù)據(jù)與表示方法分離，可以獨立研究數(shù)據(jù)的表示問題。在可視化部分，輸入為源節(jié)點表和節(jié)點鄰接矩陣，通過選擇適當?shù)乃惴?，將?shù)據(jù)關(guān)系用圖的方式進行顯示。

計算機技術(shù)和開發(fā)環(huán)境的日益提高，人們對圖形化的界面技術(shù)要求也越來越高，平面圖的應用非常廣泛，因此一定要有良好的平面圖表示技術(shù)。通過將平面圖繪制技術(shù)用于數(shù)據(jù)可視化，并與數(shù)據(jù)平臺相結(jié)合，進行數(shù)據(jù)組織與分析，對滿足各種應用的需求潛力巨大。

[1]翟金剛,張教軍.基于極大平面圖矩形圖元布局問題的全局優(yōu)化算法 [J].魯東大學學報 (自然科學版)，2010,26(4): 293-296.

[2]Kumar P.Graph Visualization and its Applications[D].Ph.D.thesis,The UniversityofTexas,2009.

[3]SHEN Z.Visual Analysis ofComplex Social Networks[D].Ph.D.thesis,Dept.of Computer Science,University of California, 2009.

[4]Healy P,Nikolov N S.Applications of Parameterized st-Orientations in Graph Drawing Algorithms[J].Graph Drawing, Lecture Notes in Computer Science,2006,Volume 3843/2006, 355-367.

[5]王曉白，王 歡,等.UML類圖層次化自動布圖算法[J].軟件學報，2009，20（6）：1497-1498.

[6]張軍英，覃 強，等.平面化問題的一種新型神經(jīng)網(wǎng)絡算法[J].中國科學E輯:信息科學，2008，38（12）：2163-2172.

[7]劉纘武.應用圖論[M].國防科技大學出版社，2006.

[8]趙長虹.超大規(guī)模集成電路的平面布圖規(guī)劃算法研究[D].復旦大學博士學位論文，2006.

（責任編輯：魏樹峰）

Research and Implementation of Planar Graph Drawing Algorithm

WANG Yin-yuan
（Wujin Open University,Changzhou 213149,China）

The node drawingsequence and nodal coordinates ofplanar graph drawingare studied.The twomethods of node drawingsequence,i.e.canonical sequence and canonical decomposition,are presented.Based on the above study,the specific algorithmofdrawingis illustrated and its applications are addressed.

planar graph;canonical sequence,canonical decomposition,straight line drawing;convexdrawing

TP311.11

A

2016－10－03

王銀媛（1980-），女，江蘇常州人，講師，研究方向：計算機程序設計與開發(fā)、計算機軟件應用。E-mail:meidxidowx@126.com．

1671－802X(2016)06－0028－05