PARTITIONING A SEQUENCE INTO FEW MONOTONE SUBSEQUENCES

In this paper we consider the problem of finding sets of long disjoint monotone subsequences of a sequence of n numbers. We give an algorith m that, after O(n log n) preprocessing time, finds and deletes an incr easing subsequence of size Ic (if it exists) in time O(n + k(2)). Usin g this algorithm, it is possible to partition a sequence of n numbers into 2[root n] monotone subsequences in time O(n(1.5)). Our algorithm yields improvements for two applications: The first is constructing go od splitters for a set of lines in the plane. Good splitters are usefu l for two dimensional simplex range searching. The second application is in VLSI, where we seek a partitioning of a given graph into subsets , commonly refered to as the pages of a book, where all the vertices c an be placed on the spine of the book, and each subgraph is planar.