|
Vertex partitioning of graphs is applied to the "divide-and-conquer" approaches for solving combinatorial problems. The underlying concept in the method is to divide the original problem into independent multiple subproblems for roughly the same size. The subproblems are then solved recursively and combined to provide a solution to the large problem. The planar separator theorem of Lipton and Tarjan provides a basis of this approach. However, there is a "bottleneck" in the process of partitioning a very large graph, this bottleneck appears in the planarity testing operation. Before a graph is partitioned, certain planarity breaking arcs need to be extracted, and the planar embedding for a large graph is extremely time and space consuming. The main purpose of this research is to develop an efficient planar embedding algorithm for planar graph partitioning. The major contributions of this thesis are summarized: (1) The planarity testing algorithm proposed by Hopcroft and Tarjan with complexity σ(N) is modified in order to make the construction of a planar representation. This approach is to replace the previous algorithm which was the Demoucron el al. planar embedding algorithm with complexity σ(N). where N is the total number of vertices in the graph. (2) The proposed algorithm is used to improve the efficiency for planar graph partitioning. (3) A graphical interface is developed to provide user-friendly operation environment for graph-theoretic algorithms.
|