An optimal vertex ranking of a permutation graph can be computed in time O(n tothe 6th power), where n is the number of vertices. The demonstrated method can be used for designing polynomial time algorithms computing an optimal vertex ranking on the following classes of well-structured graphs too: circular permutation graphs, interval graphs, circular arc graphs, trapezoid graphs and cocomparability graphs of bounded dimension.
展开▼
