@Article{BarFog97,
    author  =	"R. Bar-Yehuda and S. Fogel",
    title   =	"Partitioning a Sequence into Few Monotone Subsequences",
    journal =	"Accepted  to Acta Informatica",
    abstract=   " In this paper we consider the problem of finding
		  sets of long disjoint monotone subsequences of a sequence of
		  $n$ numbers. We give an algorithm that, after $O(n \log n)$
	     preprocessing time, finds and deletes an increasing
	     subsequence of size $k$ (if it exists) in time $O(n + k^2)$. 
	     Using this algorithm, it is possible to partition 
	     a sequence of $n$ numbers into $2 \lfloor \sqrt n \rfloor$
	     monotone subsequences in time $O(n^{1.5})$. 
		        
	     Our algorithm yields improvements for two applications: The
	     first is constructing good splitters for a set of lines in the
	     plane. Good splitters are useful for two dimensional simplex
	     range searching. The second application is in VLSI, where we
	     seek a partitioning of a given graph into subsets, commonly 
	     referred to  as the pages of a book, where all the vertices
	     can be placed on the spine of the book, and each subgraph is 
	     planar.",
}