叢集圖形平面化問題之改良啟發式演算法

叢集圖形平面化是藉由添加啞交叉點至叢集圖形的底層圖形，使其轉換成具備叢集平面性質的叢集圖形的一系列操作。平面化的啟發式演算法含兩階段：暫除邊而得到具平面性質的子圖，然後將暫除的邊經平面化操作再補回圖形。其中第二階段一般牽涉到在機件圖形上的路徑搜尋。衡量平面化演算法的準則為產生的啞交叉點個數。叢集圖形平面化的經典啟發式演算法將暫除邊補回圖形時保持叢集邊界圈。但構造叢集邊界圈會對每個叢集的外延邊的循環次序造成多餘限制，阻礙了潛在的良好嵌入以及其上所能找到的更好的解。本論文提出針對叢集圖形平面化問題的改良啟發式演算法。構造叢集邊界圈的步驟拆作構造叢集邊界點及叢集邊界邊兩部分，其中叢集邊界邊的存在會對叢集外延邊的循環次序造成多餘限制。因此本論文提出的改良啟發式演算法將構造叢集邊界邊的步驟延後到暫除邊補完之後才實際構造。在此之上，構造並擴充捷徑機件子圖至機件圖上，使得在此擴充機件圖上尋找最短加權路徑即等價於在眾多嵌入中尋找單邊補回的最佳解。本論文分別從理論及實驗兩方面檢驗此改良演算法。從理論角度驗證，此改良演算法中的單邊補回方法，對於叢集連通的叢集圖形，能夠解得其某類嵌入集下的單邊補回問題的最佳解。而從實驗角度驗證，此改良演算法確實勝過經典演算法，總和來看改良演算法所致生的啞交叉點個數縮減為經典演算法所致生的啞交叉點個數的 89.1% 。

關鍵字

叢集圖形；圖形平面化

並列摘要

Planarization of clustered graph is a series of operations to transform the underlying graph by creation of degree four crossing dummies such that the result becomes a c-planar clustered graph. The heuristic for planarization consists of two stages: finding a subgraph by discarding some edges, and then reinsert discarded edges back through planarization operations. The edge reinsertion stage generally involves path finding on certain gadgets. The criteria of planarization is to minimize the number of incurred crossing dummies. The classic method for planarization of clustered graph deal with this problem by starting from a maximal c-planar sub-clustered graph and then repetitively doing single edge insertion while maintaining cluster boundary cycles. But the modeling of cluster boundary cycles put unnecessary constraint on the cyclic ordering of outgoing edges of each cluster, hence prohibit some potentially good embeddings in which better solution can be found. The thesis proposes an improved heuristic algorithm for planarization of clustered graph. In the thesis, the modeling of cluster boundary cycles breaks into modeling of boundary points and boundary edges, and the modeling of boundary edges are deferred after edge reinsertion stage has been finished. Moreover, shortcut gadgets are augmented to the gadget such that searching a shortest weighted path on the augmented gadget is effectively finding an optimal solution for single edge insertion amongst more embeddings at once. The proposed method is both theoretically and experimentally examined. Theoretically that the proposed method finds an optimal solution for single edge insertion among a certain type embedding set for a c-connected clustered graph. And experimentally that the proposed method does outperform the classic method in the sense that the overall average of incurred crossings is reduced to about 89.1% in the experiment.

並列關鍵字

Clustered Graph ； Planarization

參考文獻

[BDM02] Giuseppe Battista, Walter Didimo, and A. Marcandalli. Planarization of clustered

[BETT98] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. Graph

[BGL + 97] Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Roberto Tamassia, Emanuele

[CDF + 08] Pier Francesco Cortese, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani,

graphs. In Petra Mutzel, Michael Jünger, and Sebastian Leipert, editors, Graph

國際替代計量

叢集圖形平面化問題之改良啟發式演算法

全文下載

主題瀏覽