Algorithm Engineering for Structural Graphs

这个项目的目的是建立“设计有效的结构化图算法的范例”。我们通过研究结构化图中树、串并图、部分κ树的未解决问题，成功地找到了着色、不相交路径、图绘制的有效算法，具体如下：-给出了在O(n^2log)时间内对任意正整数c找到给定树T的最优c-边排序的算法，其中n是T中的顶点数；-给出了当所有终端都在双连通平面图G的外表面上时，在O(n-logn)时间内找到不相交的Steiner森林的算法；给出了在O(n^2log)时间内求给定树T的最优c-边排序的算法，其中n是T中的顶点数，是树的最大顶点度。该算法比最著名的c=1的情况更快：-证明了边不相交的路问题对于部分κ-树是NP-完全的，尽管这个问题对于树来说是平凡可解的；-给出了一个线性时间算法来寻找给定的3连通三次平面图的具有最少弯数的正交图。最著名的算法对任意n个顶点的平面图都需要O(N7/4√&lt；logn&gt；)时间.自1987年以来，我们致力于发展“结构图的高效算法设计范例”，并成功地给出了许多困难问题的最佳可能算法.我们相信，我们为巩固这一研究领域的基础做出了巨大贡献。

This project aimed to establish "Paradigm for Designing Efficient Algorithms on Structured Graphs." We approached the project by taking up the unresolved problems of trees, series-parallel graphs, partial κ-trees in structured graphs, and succeeded in finding the efficient algorithms for colorings, disjoint paths, graph drawings, as follows :-gave an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n^2log△), where n is the number of vertices in T ;-gave an algorithm for finding a noncrossing Steiner forest in O(n log n) time in the case that all terminals are on the outer face of a biconnected plane graph G ;-presented an algorithm to find an optimal c-edge-ranking of a given tree T for any positive integer c in time O(n^2log△), where n is the number of vertices in T and △ is the maximum vertex-degree of T.This algorithm is fater than the best known for the case c=1 :-proved that the edge-disjoint paths problem is NP-complete for partial κ-trees with some bounded κ, say κ=3, although the problem is trivially solvable for trees ; -gave a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n7/4 √<logn>) for any plane graph of n vertices.Since 1987 we have devoted ourselves to develop "Paradigm for Designing Efficient Algorithms on Structured Graphs" and succeeded in giving the best possible algorithms for many difficult problems. We are confident that we made a great contribution to consolidating the foundations of this research field.