Multilevel Unbalanced Graph Partitioning with Applications to Graph Drawing
Date Issued
2007
Date
2007
Author(s)
Lin, Shu-Fen
DOI
en-US
Abstract
The graph partitioning problem arises in many areas of computer science, including the application to graph drawing. In graph drawing, a good layout explicitly shows the relationship between all nodes. We present a graph partitioning algorithm based on tree partitioning to clearly separate one cluster from another, make some adjustments on clusters and find the best partition. Finally, we use force-directed placement algorithm to demonstrate the result in a visual form. The traditional solution to k-way partition is to find bisection recursively and generalize it into k partitions. We demonstrate another algorithm to divide the graph into k parts directly with some adjustments. These two ways for the k-way partition problems are compared empirically later.
Our contributions lie in providing a graph partitioning algorithm from different perspectives with lower complexity than before. In addition, we can find the number of clusters approximately using the algorithm presented in this thesis. While applied in graph drawing, this algorithm could reduce the number of steps in a force-directed placement algorithm.
Subjects
多層次非均衡圖形切割
樹切割
移動演算法
圖形繪製
multilevel unbalanced graph partitioning
tree partitioning
shifting algorithm
graph drawing
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R94921090-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):f708fd55982216251e3c50810220eace