Decomposing a set of points into chains, with applications to permutation and circle graphs (Q1071505)

An O(n log n) time algorithm is given to partition a set of n points in the plane into a minimum number of ascending chains. This result is then used to derive O(n log n) time algorithms for a number of problems concerning permutation graphs including minimum coloring - thus improving on the \(\Theta (n^ 2)\) time algorithm of \textit{S. Even, A. Pnueli} and \textit{A. Lempel} [J. Assoc. Comput. Mach. 19, 400-410 (1972; Zbl 0251.05113)]. This coloring algorithm is in turn used to derive an O(n log n) time heuristic for coloring circle graphs, with a performance guarantee (the worst-case ratio between the number of colors it uses and the chromatic number of the graph) of O(log n).