Biconvex graphs: Ordering and algorithms (Q1570816)

The authors show that the vertices of biconvex graphs have a so called S-ordering that is biconvex and generalizes a strong ordering property that is achievable for bipartite permutation graphs. A graph is biconvex when it is bipartite and allows a biconvex ordering, i.e., both bipartite sets can be ordered such that for every vertex its neighbours occur consecutively in the ordering. Moreover, a parallel algorithm is given that allows to find an S-ordering efficiently. Some applications of this result are shown. For an example the polynomial time solvability of the vertex ranking problem on biconvex graphs. This problem is to find a coloring of the vertices using a minimal number of colors such that every path between two vertices of the same color must contain a vertex with a higher color.