A Study on Efficient Graph Algprithms and their Evaluation

点击翻译按钮获取中文摘要

In this project, we first deal with the coloring, total coloring, multicoloring, list edge-coloring, edge-disjoint paths, and partitioning problems on structured graphs such as trees, seriesparallel graphs, partial κ-trees and degenerate graphs, and design and analyse efficient algorithms for these problems. We then investigate the drawing problems of plane graphs.For trees, we obtain an algorithm to solve the cost edgecoloring problem in time ο(nΔ^2), and give a pseudo-polynomial time algorithm and FPTAS for the partitioning problem. For series-parallel graphs, we obtain algorithms for the weighted coloring, multicoloring, list edge-coloring problems. We also succeed in proving the NP-completeness of the edge-disjoint paths problem on series-parallel graphs. For partial κ-trees, we give an algorithm to solve the multicoloring problem in time polynomial in the number n of vertices and in the maximum weight W. For degenerate graphs, we obtain an efficient algorithm for the total coloring problem. For planar graphs, we give an algorithm to solve the non-crossing Steiner forest problem under a 2-face condition in time ο(n log n).Concerning the graph drawing problem, we first obtain efficient algorithms to find a straight-line drawing of 4-connected plane graphs on a small grid, a rectangular drawing without designating corners, and an orthogonal drawing with the minimum number of bends, and then give a characterization of plane graphs having inner rectangular drawings.