Title: Maximum Independent Set of A Permutation Graph in $k$ Tracks* D. T. Lee and Majid Sarrafzadeh Department of Electrical Engineering and Computer Science Northwestern University Evanston, IL 60208 * Supported in part by the National Science Foundation under grants CCR-8901815 and MIP-8921540. Abstract: A maximum weighted independent set of a permutation graph is a maximum subset of noncrossing chords in a matching diagram (i.e., a set $\Phi$ of chords with end-points on two horizontal lines). The problem of finding, among all noncrossing subsets of $\Phi$ with density at most $k$, one with maximum size is considered, where the density of a subset is the maximum number of chords crossing a vertical line and $k$ is a given parameter. A $\Theta (n\log n)$ time and $\Theta (n)$ space algorithm, for solving the problem with $n$ chords, is proposed. As an application, we solve the problem of finding, among all proper subsets with density at most $k$ of an interval graph, one with maximum number of intervals. Keywords: Permutation graphs, maximum independent set, maximum chain, track assignment, plane sweep technique. Int'l J. Comput. Geometry & Applications, (3,3) Sept. 1993, 291-304.