| The objective of this work is to develop good approximation algorithms for two NP-hard graph-theoretic problems: Multiway Cut and Maximum Weight Planar Subgraph. Connectivity and planarity are important concepts in graph theory. Graphs are used to model many real-world situations. The problems addressed in this thesis have applications in parallel and distributed computing, chip design, graph drawing, circuit layout, and facility layout.;Multiway Cut is the following problem: given an undirected graph with nonnegative edge costs and a subset of k nodes called terminals, find a cheapest multiway cut, i.e., a subset of the edges whose removal disconnects each terminal from the other terminals. Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis gave a performance ratio of 2 ( 1-1k ). In this thesis, a new approximation algorithm is presented. The algorithm breaks the threshold of 2 for approximating Multiway Cut, achieving a performance ratio of at most 1.5-1k .;Maximum Weight Planar Subgraph is the following problem: given an undirected graph G with nonnegative edge weights, find a planar subgraph of G of maximum weight. No previous polynomial-time algorithm for this problem was known to achieve a performance ratio exceeding 1/3. Moreover, a performance ratio of 1/3 is not hard to achieve. In this thesis, the first algorithm with a nontrivial approximation ratio for Maximum Weight Planar Subgraph is presented. Based on the Berman-Ramaiyer Steiner tree algorithm, the new algorithm breaks the 1/3 threshold. It is also shown that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8. |
