To place labels on a digital map, indications of dimensions and positions for candidate labels for placement within a bounded region of a digital map are received. The bounded region is partitioned into bands parallel to an axis. For each of the bands, a respective subset of the candidate labels is identified, such that such that each label in the subset is at least partially disposed in the band. Non-overlapping labels are iteratively selected from the subset based at least on one of the edges of the labels in the subset perpendicular to the axis. A result set if generated using the respective selections of non-overlapping labels for the bands. The labels in the result set are placed on the digital map.