Paradigm for Designing Efficient Algorithms on Structured Graphs

该项目旨在建立“在结构图上设计高效算法的范例”。“我们通过解决结构图中树、串-并行图、partialk-tree的未解决问题来接近该项目，并成功地找到了着色、不相交路径、图形绘制的有效算法，如下所示：-给出了一个算法来找到给定树T的最佳c-边-ranking对于任何正整数c在时间OMICRON（n^2 logDELTA），其中n是T中的顶点数;- 给出了一个在OMICRON上运行的寻找非交叉Steiner森林的算法在所有终端都在双连通平面图G的外表面上的情况下的（eta log eta）时间;- 提出了一个算法，以找到一个最佳的c-边排序的给定树T的任何正整数c在时间OMICRON（n^2 logDELTA），其中eta是T中的顶点数，DELTA是T的最大顶点度。- 证明了边不相交路径问题对于部分kappa树是NP-完全的，且kappa有界，比如kappa = 3，尽管这个问题对于树是平凡可解的;-给出了一个线性时间算法，以找到给定的3-连通三次平面图的具有最少弯曲数的正交图。对于任意eta顶点平面图，最著名的算法需要时间OMICRON（eta^<7/>ROO<log eta>）.自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, partialk-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 OMICRON(n^2 logDELTA), where n is the number of vertices in T ;- gave an algorithm for finding a non crossing Steiner forest which runs in OMICRON(eta log eta) 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 OMICRON(n^2 logDELTA), where eta is the number of vertices in T and DELTA 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 kappa-trees with some bounded kappa, say kappa = 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 OMICRON(eta^<7/>ROO<log eta>) for any plane graph of eta 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 some difficult problems. We are confident that we made a great contribution to consolidating the foundations of this research field.