A Study on Efficient Graph Algprithms and their Evaluation

在本课题中，我们首先处理了树、序列并行图、部分树和退化图等结构化图的着色、全着色、多重着色、列表边着色、边不相交路径和划分问题，并设计和分析了这些问题的有效算法。然后我们研究了平面图的绘制问题。对于树，我们得到了一种在时间0 （nΔ^2）内解决代价边着色问题的算法，并给出了分区问题的伪多项式时间算法和FPTAS。对于序列-并行图，我们得到了加权着色、多重着色、列表边着色问题的算法。我们还成功地证明了级数并行图上边不相交路径问题的np完备性。对于部分κ树，我们给出了一个在n个顶点和最大权值w的时间多项式上解决多着色问题的算法。对于退化图，我们得到了一个解决全着色问题的有效算法。对于平面图，我们给出了在时间为ο(n log n)的2面条件下求解不相交斯坦纳森林问题的算法。在图的绘制问题上，首先给出了在小网格上求四连通平面图的直线图、不指定角的矩形图和弯数最少的正交图的有效算法，然后给出了具有内矩形图的平面图的表征。

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.