Joseph Marks and Stuart Shieber. The Computational Complexity of Cartographic Label Placement. Technical Report TR-05-91, Center for Research in Computing Technology, Harvard University, 1993. (pdf) (bibtex: Marks-1993-CCC).