A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

摘要

An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges e_u, e_v with the same rank r(e_u) = r(e_v) contains an intermediate edge e_w with rank r(e_w) > r(e_u). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph.