A special class of map labeling problem is studied. Let P = {p 1,p2,...,pn} be a set of point sites distributed on a 2D map. A label associated with each point pi is an axis-parallel rectangle ri of specified width. The height of all ri,i = 1,2,...,n are same. The placement of ri must contain pi at its top-left or bottom-left corner, and it does not obscure any other point in P. The objective is to label the maximum number of points on the map so that the placed labels are mutually non-overlapping. We first consider a simple model for this problem. Here, for each point p i, the corner specification (i.e., whether the point pi would appear at the top-left or bottom-left corner of the label) is known a priori. We show that the time complexity of this problem is Ω(n log n), and then propose an algorithm for this problem which runs in O(n log n) time. If the corner specifications of the points in P are not known, our algorithm is a 2-approximation algorithm. Here we propose an efficient heuristic algorithm that is easy to implement. Experimental evidences show that it produces optimal solutions for most of the randomly generated instances and for all the standard benchmarks available in http://www.math-inf.uni-greifswald.de/map-labeling/. © 2003 Elsevier B.V. All rights reserved.