An Efficient Algorithm for Scatter Chart LabelingSebastian Theophil

Arno Schödlsebastian@theophil.net
Institut für Informatik
Humboldt-Universität zu Berlin
Unter den Linden 6
10099 Berlin
Germany

aschoedl@think-cell.com
think-cell Software GmbH
Invalidenstr. 34
10115 Berlin
Germany

Abstract
This paper presents an efficient algorithm for a new variationof the point feature labeling problem. The goal is to position
the largest number of point labels such that they do not intersect each other or their points. First we present an algorithm
using a greedy algorithm with limited lookahead. We thenpresent an algorithm that iteratively regroups labels, callingthe first algorithm on each group, thereby identifying a close
to optimal labeling order. The presented algorithm is being
used in a commercial product to label charts, and our evaluation shows that it produces results far superior to those ofother labeling algorithms.

Introduction
The problem of labeling points in the plane has been studied
extensively. In its simplest form, the so-called point feature labeling problem (PFLP) consists of a set of points,
each with a corresponding label. Each label can be placed
at a discrete number of positions. Label-label intersections are not allowed. This problem was first describedin the context of labeling geographic maps (Imhof 1975;
Hirsch 1982). An alternative formulation called the sliding label model (van Kreveld, Strijk, & Wolff 1999) allows the labels to be placed at any position as long as it
touches its point. Both instances have been shown to be NPcomplete (Marks & Shieber 1991; Formann & Wagner 1991;
Iturriaga & Lubiw 1997). Naturally, when more label positions are available, labeling results improve and more labels
can be placed. In (van Kreveld, Strijk, & Wolff 1999) a
2-approximation algorithm is developed that has been extended in (Strijk & van Kreveld 1999) to place labels withvarying height while respecting line-type geometric constraints. Very recently, a force-based labeling algorithm has
been proposed in (Ebner, Klau, & Weiskircher 2003) showing excellent results when compared to the sliding label 2approximation algorithm. It performed even better than simulated annealing, which performed best in the survey paperby Christensen et al. (Christensen, Marks, & Shieber 1995).
From a user’s perspective, all these approaches sufferfrom a serious drawback. Even small dense problem instances as in Fig. 1 cannot be labeled satisfactorily because
Copyright c 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.

Figure 1: Simple problem instance were PFLP algorithms
fail (left) and a possible resolution (right).

label positions are restricted to positions adjacent to eachlabel’s point. In most real-world cases however, the points
will not be evenly distributed in the plane but they will concentrate in high-density clusters. We define a scatter chart asa set of points with rectangular labels, each of arbitrary dimensions. It is not only common among business charts but
also among scientific illustrations. User expectation in sucha chart is to show all labels the user has defined, if necessary
with leader lines. We found that often, leader lines improve
legibility in dense and hence confusing cases because they
make the relation between a point and a label explicit. Thus,
scatter chart labels can be placed at an arbitrary position but
when a label is not adjacent to its point, both have to be connected by a leader line.
We therefore propose an algorithm for the scatter chartlabeling problem (SCLP) which is an extension of the classic PFLP. Constraints disallow intersections between points,
labels and leader lines. Additional constraints may include
chart axes and their respective labels. Two criteria need to be
optimized when searching for a scatter chart labeling: First,
the number of placed labels must be maximized, and second,
the total length of all leader lines must be minimized.
Since the algorithm is meant to be used in an interactive
setting, to avoid user confusion, it must produce the samelabeling in every run on the same problem. Thus, algorithms must be made deterministic if necessary. Of course,
the interactive application setting also demands a fast algorithm which is able to produce results at interactive speed.
In a real-world application it is also necessary to allow user
control of label placement as argued by (do Nascimento &Eades 2003) and implemented by (Müller & Schödl 2005).
SCLP is shown to be NP-hard by reduction of discrete
PFLP but the SCLP problem is much more complex than thediscrete or sliding label PFLP problem. The search spaceof allowed label positions is much larger, and labeling de-

Y

$%

+

*

)

BA=]@A@8=A9\E24.7-E.

BA=A29.<674
1233-45

BA=O0P0.-7Z=O-0P

D27567=124.72P
BA=O0P0.-7Z=O-0P,-./0I23-40@8LA=#DMAW46.
D0236.70E=@F=NLI 1233-45
FAAOH=# ULIGB,LA
164.67@8LA=#
C>8M=@FA BA=]@A@8=A9\E24.7-E.
BA=FUA!$ BA=C-/Z
BA=U9;:Z?96P=16PP;
F-40;<
BA=F6Q64;6=,2R0;.0E;
F?=@8M
>A@
D0236.70E=@F=BG >A@
D27567=124.72P
D0236.70E=@F=IBA
D0236.70E
BA=C-/Z
1-4-5@F=LAH?96P=16PP; BA=?27E6;=86P6E23=L972S6
B[\6:0;.-4
D0236.70E
1233-45
C-.2 HG@K=CLFA@F=LAH
1L,,F>I
D27567=124.72P
164.67
CL81LC8A
1-4-5B[\6:0;.-4
C6T=C>8M=UV
BA=U9;:Z 1233-45
C>8M=! >NA ,0.<9-40164.67
1233-45=164.67>8,>A
HI@A=1JULIGB,LA
1L,,F>I>8,>A
N673-4=11@A
897:0;<=8>?@A
NLIO>C=11@A
IBD@C,0.<9-40IBD@C
CL81LC8A
1233-45=164.67
BA=A29.<674
BA=I632.6=D27567
D0236.70E=@F=IBA BA=C27.<674 1233-45
A97/60PP-4E6
D27567

(

'

&

"

#

$

%

!$

!i
φi
pi

!k
!j

Figure 3: The scatter chart labeling problem.
ri,j

C>8M=@FA

F@AC=FNA

di

!#

!"
!"

!#

!$

%

$

#

"

&

'

(

)

*

+

!k

$%

Figure 2: Example for a dense scatter chart and its labeling.
X!icisions may have large-scale effects, because especially in
difficult cases, labels are no longer necessarily close to theirpoints.

pi

Figure 4: Representing a ray ri,j as an interval set Ii,j containing the intervals of free label positions (solid lines).

Solution Idea
In the sliding label model described by van Kreveld et al.
the set of points of possible label centers form a rectangle
around the point to be labeled. By clipping the rectangle’s
four line segments, the label can be constrained to positions
where it does not intersect other labels or general line features. Our algorithm extends and generalizes this idea. In
order to treat the complexity of the SCLP problem we discretize the angles at which labels can be placed around theirpoint. A set of rays originating at each point define possible
positions of the label center. Each ray carries information offree label position intervals along the ray, at which the label
rectangle does not intersect other features. Whenever the algorithm fixes a label position, it updates the free intervals ofrays belonging to other labels. We found 128 rays to result inaesthetically very pleasing solutions. At this resolution, theeffect of only allowing discrete angles is not noticeable. We
tried fewer than 128 rays but the results were less pleasing
both by subjective human judgment as well as by objective
measures when the number of rays became too small (< 32).
We solve the SCLP problem by using two largely independent algorithms. The first algorithm calculates the actual
point labeling. When placing a label, the algorithm leaves asmuch space as possible for the remaining labels to be placed.
Therefore, for each label placement, we need a measure forthe remaining amount of valid label positions. We use the integral of a strictly decreasing function over the free intervalsof a ray as a measure of this ray’s free space. Consequently,
the sum of all ray integrals belonging to one point is a measure for a label’s free space. At each step of the algorithm,
the decision which label to place is made based on maximizing the minimum remaining space for any other label. This
limited lookahead is not sufficient to prevent obstruction ofsubsequently placed labels. The second algorithm improves
the results of the first algorithm by finding a point partitioning into subsets and an order in which to pass these subsets
to the first algorithm for labeling.

The RayIntersection Algorithm
We first describe the algorithm used to solve the problem offinding a valid labeling for a given set of points. A set ofavailable points P ⊆ P0 is given, P0 being the set of all
points which need to be labeled, and each pi ∈ P has a label`i .
The position of each label `i can be described in polar
coordinates (φi , di ) (Fig. 3). The SCLP problem can be defined as the problem of assigning pairs (φi , di ) to as manylabelsP`i as possible, such that the total length of all leaderlines i di is minimized while avoiding intersections between labels, their leader lines and all points.
As already described, the main idea is to allow only a setof discrete values for the label’s polar angle φi . Thus, eachpoint pi ∈ P consists of a set of R rays where the j-th rayri,j has an angle of φi,j = 2π/R·j, alternatively represented
as the unit vector ~vi,j .
The rays define possible positions of the label center.
On each ray ri,j , the free label positions are a set of intervals Ii,j as illustrated in Fig. 4. We define di,j :=min{a | [a, b) ∈ Ii,j } as the free label position closest
to point pi on ray ri,j . Initially, all intervals in which labels `i intersect other points are removed from Ii,j . Givena point pk and a label `i on ray ri,j with the associatedvector ~vi,j , the function L ABEL P OINT I NTERSECTION computes the interval [a, b) in which labels intersect the point:∀ t ∈ [a, b) area(`i translated by ~vi,j · t) ∩ area0 (pk ) 6= ∅.
The function sets b = ∞ if vector ~vi,j itself intersects pk ,which means that the label cannot be moved beyond the obstructing point without causing its leader line to intersect
this point. A similar function L ABEL R ECTANGLE I NTER SECTION is also defined which, given a label `k and a label`i on ray ri,j with the associated vector ~vi,j , computes theinterval [a, b) such that translating `i by ~vi,j ·t with t ∈ [a, b)
makes `i and `k intersect. L ABEL R ECTANGLE I NTERSEC TION includes the connecting line of `k in the computation

φmin
φmax

xC − xA

rA
B
r

C
ci

Figure 5: Computing the minimum and maximum angles
φmin and φmax for intersecting ci with a line. φmin =− arcsin((xC − xA )/||AC||) − arcsin(r/||AC||).

of [a, b). This algorithmic framework would allow for different label-to-leader line attachments as long as the attachments are fixed a-priori, depending on leader line direction.
Optimizing over leader line attachments would significantly
add to the running time of the algorithm.
After initialization, the algorithm repeatedly chooses apoint pi and one of its rays ri,j for labeling. It places thelabel at the location di,j , the closest free location on ray ri,j .
As stated above, this choice should be made to minimize theimpact on the remaining label positions. This criterion requires a measure for the available label space at each point.
The remaining label positions at a point pi are defined by
the set of intervals Ii,j for each ray ri,j . To derive a measure
for available space from these intervals, a strictly
decreasing
Rfunction f (x) is chosen and the integral Ii,j f (x) dx overIi,j is calculated for each ray ri,j . We chose f (x) = e−ax
because it is easy to integrate in closed form. Since f (x) is
strictly decreasing, closer label positions are preferred overlabel positions farther from pi . Summing up the integrals
over all rays of point pi gives aRmeasure of the amount ofremaining label positions called pi .
This measure forms the basis for algorithm F IND B EST R AY shown on page 4. The algorithm is given a set P ⊆ P0
and iterates over all pi ∈ P . For each point pi , it considers
only the set of best rays R, i.e., the rays whose closest free
position di,j is minimal (within some bound to account for
rounding errors). For each of these rays ri,j ∈ R, the label `iis moved to di,j resulting in label `0i . In the following loop,`0i ’s impact on all other labels `k of points pk ∈ P0 \ {pi }is calculated. For every ray rk,l of every point pk , k 6= i,the algorithm computes the intersection interval J of label`k moving along the ray rk,l with label `0i . We then computethe integral of f over Ik,l \ J as a measure of the remaining label spaceRafter obstruction by label `0i . This results
in a new total pk − for each point pk which is stored in
the list Vi,j . Thus, Vi,j contains a measure for each point
pk representing the remaining label space after label `i isplaced on ray ri,j . Now, F IND B EST R AY chooses the ray
max∀i,j {minv∈Vi,j {v}} which maximizes the minimum remaining label space for any label.
We use two observations to significantly reduce the runtime of our algorithm. Typically, the intersection tests are

performed successively for all rays of a point. Thus, thecomputation time of our algorithm is dominated by the calculation of intersection intervals. It is therefore worthwhile
to implement a fast rejection called P RE I NTERSECT, which
determines for which rays an intersection can occur at all. In
all our intersection tests, a label rectangle `i is translated bya certain vector ~v and intersected against circle, rectangle orline objects. We can approximate the label rectangle `i by an
enclosing circle ci and compute the minimum and maximum
angle φmin and φmax for the vector ~v in between which theapproximating circle ci intersects the object (Fig. 5). Then,the exact intersection tests need to be performed only forrays ri,j with φmin ≤ φi,j ≤ φmax .
The second observation is that we can
R abort the calculation of Vi,j as soon as we encounter a pk − less than theminimum of the best currently found Vbest . Stopping theevaluation as early as possible gives a significant speed improvement. In order to find a good candidate ray earlier andthus reject later rays quicker, pi ∈ P are sorted in the beginning according to their initially available space in descending order. A label `i which has a lot of available space islikely to produce a better solution than any other label because it cannot obstruct other label positions.
The final R AY I NTERSECTION algorithm on page 4 is very
short. When a ray rbest = ri,j belonging to a point pi andlabel `i has been found, the label is placed at position ~vi,j ·di,j . Placing a new label limits the available label positionsof all other points. This needs to be reflected in the interval
sets Ik,l of every ray rk,l of every point pk ∈ P0 , i 6= k.
The method L ABEL R ECTANGLE I NTERSECTION computes
the corresponding intersection interval [a, b) which is thenremoved from Ik,l . R AY I NTERSECTION is computable inO(|P0 |3 R2 ) where R is the constant number of rays. Dueto several optimizations we found its average complexity tobe O(|P0 |2 R2 ).

The IterativeGreedy Algorithm
The number of successfully placed labels can be improved
over the naive application of R AY I NTERSECTION by adapting the order in which labels are placed. The top-level
I TERATIVE G REEDY algorithm is shown on page 5. R AYI NTERSECTION is called first on P0 . This may result in aset of unlabeled points N , when the limited lookahead was
unable to maintain free label positions for all labels. Often,these points in N are in dense clusters which are difficult
to label. Therefore, it is a good idea to label the points in
N first. Thus, R AY I NTERSECTION is first called on N andthen on the remaining points P0 \ N . Generalizing this approach, let Pi be a queue of point sets. Initially, all points
are in P0 . Assuming there were n non-empty point sets
P0 , . . . , Pn−1 , R AY I NTERSECTION is subsequently calledon each set, starting with Pn−1 . If for any point set Pi , after calling R AY I NTERSECTION, a non-empty set N of unlabeled points is returned, the points in N are promoted
to the group Pi+1 which is labeled earlier in the next iteration. When a partition into point sets P0 , . . . , Pn−1 isfound such that all points can be labeled, the labeling result can often still be improved by promoting the label with

Algorithm 1: FindBestRay Algorithm
Input: A set of points pi ∈ P ⊆ P0 with rays ri,j foreach point pi .
Output: The best ray rbest to be labeled next.
R
1 sort pi ∈ P by available spacepi in descending order;
R minp← INT MAX;2
3 rbest ← nil;
4 Vbest ← ∅;foreach pi ∈ P do
R ← { ri,j | di,j = min∀k {di,k } + const};
7
foreach ri,j ∈ R do
8
Vi,j ← ∅;9`0i ← `i + ~vi,j · di,j ;
5

6

10
11
12
13
14

15
16
17
18
19
20
21

foreachpk ∈ P0 \ {pi } doR −pk ← 0;(φmin , φmax ) ← P RE I NTERSECT(`0i , `k );foreach ray rk,l of pk withφmin ≤ φk,l ≤ φmax do
J ← L ABEL R ECTANGLE I NTERSEC TION (`0 , `k , rk,l );R − i R − R
pk ← pk + Ik,l \ J f (x) dx;
endRR
if rbest 6= nil ∧ pk − < pmin thencontinue with ri,j+1 ;endRVi,j .push( pk − );end

if Vi,j < Vbest in lexicographic order then23
rbest ← ri,j ;24← Vi,j ;RVbest25
pmin ← min{v ∈ Vbest };
26
end
27
end
28 end29 return rbest ;22

the longest distance from its point. The algorithm continues
as long as all points remain labeled and the total distanceof all leader lines decreases. If R AY I NTERSECTION returns
an optimal solution we have ¬promoted because all labels
have been placed and subsequently searching the label withthe longest connector will return nothing, i.e., all labels havebeen placed adjacent to their point. Therefore, the algorithm
can terminate in line 25.
In its simplest form, I TERATIVE G REEDY as it is shown is
not guaranteed to terminate. If a label exists that cannot evenbe placed as the first, the algorithm will loop infinitely. Thislabel will eventually be in its own label set Pi . Labeling Pi
will fail and R AY I NTERSECTION returns the set N = Pi .
In this case, the algorithm should not promote the set N ,but instead remove this label and set promoted to false. The
algorithm will then continue as if all labels have been placed.

Algorithm 2: RayIntersection Algorithm
Input: A set of points P ⊆ P0 with rays ri,j for eachpoint pi ∈ P .
Output: A set of points N ⊆ P which could not belabeled.
N ← ∅;
while P 6= ∅ do
3
ri,j ← F IND B EST R AY(P);4
Place label `i at position ~vi,j · di,j ;1
2

foreach pk ∈ P0 \ {pi } do
(φmin , φmax ) ← P RE I NTERSECT(`i , `k );5
6foreach ray rk,l of pk with φmin ≤ φk,l ≤ φmaxdo
8[a, b) ← L ABEL R ECTANGLE I NTERSEC RTION(`i ,R`k , rk,lR) ∩ Ik,l ;pk ← pk − [a,b) f (x) dx;
910
Ik,l ← Ik,l \ [a, b);
11
end
R
12
if pk = 0 then13
N ← N ∪ {pk };14
P ← P \ {pk };
15
end
16
end
17 end18 return N ;7

In another case of infinite running, the algorithm may
cyclicly revisit the same label partitions. As a simple fix,
the repeat ... until loop should be terminated after a constantnumber of iterations, returning the best solution found so far.

Evaluation
We chose to compare our algorithm’s quality and performance with the results of three algorithms, selected for being the best performer in the survey they were tested in. In
past papers, labeling algorithms have also been compared torandom placement, Hirschs original heuristic or exponential
optimal algorithms, all of which performed badly. In (Christensen, Marks, & Shieber 1995) the simulated annealing
algorithm S IM A NN with four possible label positions performed best. For the sliding label model we included boththe approximation algorithm A PPROX presented in (Strijk& van Kreveld 1999) and the more recent force-directed
algorithm FDL described in (Ebner, Klau, & Weiskircher
2003). We used the implementations by Ebner et al. thatare publicly available on the authors’ website1 . Besides thepresented F ULL A LGORITHM, we also evaluated a simpler
version of our algorithm called N O L OOKAHEAD that does
not use any lookahead. Instead, F IND B EST R AY chooses thepoint with the least free space as the next point to label. This
reduces our algorithm’s complexity to O(|P0 |2 R). All performance data was measured on an AMD Athlon64 3800+
1

http://www.ads.tuwien.ac.at/research/labeling/Algorithm 3: IterativeGreedy Algorithm
Input: A set of points pi ∈ P0 to be labeled.
1

initialize pi ∈ P0 including rays and labels;

2
3n ← 1;
breakatlocalopt ← false;4

while true do

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

∀i : Pi0 ← Pi ;i ← n − 1;promoted ← false;
while i ≥ 0 do
N ← R AY I NTERSECTION(Pi );if N 6= ∅ thenPi0 ← Pi0 \ N ;0
0
Pi+1← Pi+1∪ N;n ← n + 1;
promoted ← true;endi ← i − 1;end
if ¬promoted thenbreakatlocalopt ← true;
Find label with longest connector p ∈ Pi0 ;if p exists thenPi0 ← Pi0 \ {p} // promote label;0
Pi+1← Pi0 ∪ {p};else∀i Pi∗ ← Pi // labeling is optimal;
break;
end
end

33

if first iteration or labeling Pi better than Pi∗ then∀i Pi∗ ← Pi ;else if breakatlocalopt thenbreak // We had a complete solution already;end

34∀i Pi ← Pi0 ;

29
30
31
32

35

end

36

place labels at stored solution Pi∗ ;machine equipped with 1 GB RAM.
We compared these five algorithms first on the evenly distributed evaluation set used by Ebner et al. available on
their website at the address mentioned above. We used thesets with up to 1300 labels which were generated to be always solvable. They were indeed relatively easy to label andboth our N O L OOKAHEAD algorithm and the FDL algorithm
maintained very good results even for large numbers of labels as Fig. 6 (a) demonstrates. Our N O L OOKAHEAD algorithm performed better than FDL, A PPROX, and S IM A NN
when comparing the labeling quality. However, the tradeoff between time and quality does not seem to favor ouralgorithm (Fig. 6 (b)) as it is significantly slower than theothers. Analysis of our algorithm’s performance shows that
it is slowed down by the larger number of points as well asa larger number of iterations of I TERATIVE G REEDY. The
number of iterations increases very quickly early on, butlater levels off at 18.
As a second test set we chose labeling problems generated by a Gaussian distribution, i.e., test sets with dense
point clusters of up to 99 labels which more closely resemble real-world labeling problems, e.g. when labeling charts.
Although the examples contained relatively few labels they
proved to be very difficult as Fig. 7 (a) shows. The sets were
small enough so we could also test our F ULL A LGORITHM.
Both our scatter chart algorithms attained significantly better
results than the best competitor, the force-directed labelingalgorithm. The chart shows that our algorithms are able tofrequently place all labels, which all others, using their limited placement options, never achieve. For very large numbers of labels, there is simply not enough space to fit alllabels and the number of placed labels converges for all fivealgorithms. We chose to depict the computation time on logarithmic scale (Fig. 7 (b)) because it shows the similar runtime of N O L OOKAHEAD and FDL with N O L OOKAHEAD’slabeling quality being far superior. The A PPROX algorithm
was faster than the Java timer resolution and is therefore notincluded.
Under the measure of placed labels, the advantage of using lookahead seems small, in particular considering its performance overhead. However, we measured the total distance of all labels to their points and found that the F ULL A L GORITHM version placed more labels and it placed some atleast 20 % closer to their points than N O L OOKAHEAD (notshown).

Conclusion
The results show that our scatter chart labeling algorithm
is able to solve more difficult labeling problems with denselabel clusters than previously best competitors. Even for
evenly distributed samples the solution quality is still superior to that of any other algorithm. In addition, our algorithmic framework is flexible enough to allow for easy
adaptation to different label problems. We extended it to socalled bubble charts in which a point’s third dimension isshown as its area or diameter. For these charts, labels canbe placed inside and outside of bubbles, with the added difficulty that bubbles can partially intersect each other. It issimilarly straightforward to incorporate user input by fixing
labels to user-defined locations. These labels simply create additional obstructions initially excluded from the freeintervals. Because users expect fast response times wheninteracting with a computer, we let the algorithm computea labeling solution asynchronously, starting over whenever
the user changes the input. On multi-processor machines,
the algorithm runs in parallel.
The presented algorithm is used in a production environment encompassing over 15000 users worldwide at 120+
companies. Our users say that the quality of the automatic
labeling quality is often superior to solutions created by humans due to its greater visual regularity.

;%4("3<=.%3,>'<#%?'>24@<AB%>2CD

E?>FB)1)*@E('1B@#'G)?,/A@H>'?,BI!"#$%&'(#)%"*
9*:!"#$%&'(#)%"*
C9D

6)) *

877 9

=7 9

5) *

!"#""$%&'%(/0#!>??@.?A%1,B($%#%%&'()'*;7 9+,,-".

78 *

123+44)*6'/*%-782'-09)7#':)9,/;7<,-)
6))

E))

F))

G))

5))

66))

6E)) (#)%"*'9H:.001%2!"#:7 9
79
B,+82(0()-B'&02-$&C(,16/-D13(
34

35

67

66

6;

+,-.//
<4

(a)

<;

55

:6

;4

=4

==

(#)%"*'CJD

(a)
!"#$
789

!"#$
345
=>>>

$%#%%&'()'*

E;;;

!"#

=>>

*+,,-.,/#012'3
E;;=>+,-.//*4$

E;="#$##%&'(&).001%2
>C=

E

>C>=

513.66

;FE
>C>>=
;F;E
=>>

?>>

@>>

A>>

B>>

==>>

=?>> %&'$()*3D5

@>

@?

:;

::

:<

=>

=<

??

A:

<>

!>

!!

%&'$()*7G9

(b)

(b)

Figure 6: Results for labeling randomly distributed points.

Figure 7: Results for labeling dense point clusters.

Acknowledgments

Imhof, E. 1975. Positioning names on maps. The American
Cartographer 2(2):128 – 144.
Iturriaga, C., and Lubiw, A. 1997. Np-hardness of some
map labeling problems. Technical Report CS-97-18, University of Waterloo.
Marks, J., and Shieber, S. 1991. The computational complexity of cartographic label placement. Advanced Research in Computing Technology TR-05-91, Harvard University.
Müller, S., and Schödl, A. 2005. A smart algorithm for column chart labeling. In Butz, A.; Fisher, B.; Krüger, A.; andOlivier, P., eds., Smart Graphics: 5th International Symposium, SG 2005, Frauenwörth Cloister, Germany, volume3638 of Lecture Notes in Computer Science, 127 – 137.
Springer Verlag.
Strijk, T., and van Kreveld, M. 1999. Practical extensionsof point labeling in the slider model. In GIS ’99: Proceedings of the 7th ACM international symposium on Advancesin geographic information systems, 47–52. New York, NY,
USA: ACM Press.
van Kreveld, M.; Strijk, T.; and Wolff, A. 1999. Point labeling with sliding labels. Computational Geometry: Theory and Applications 13:21–47.

The authors would like to thank Markus Hannebauer andHans-Dieter Burkhard for their valuable input.

References
Christensen, J.; Marks, J.; and Shieber, S. 1995. An empirical study of algorithms for point-feature label placement.
ACM Transactions on Graphics 14(3):203 – 232.
do Nascimento, H. A. D., and Eades, P. 2003. User hints formap labelling. In CRIPTS ’03: Proceedings of the twentysixth Australasian computer science conference on Conference in research and practice in information technology,
339–347. Australian Computer Society, Inc.
Ebner, D.; Klau, G. W.; and Weiskircher, R. 2003. Forcebased label number maximization. Technical Report TR186-1-03-02, TU Wien.
Formann, M., and Wagner, F. 1991. A packing problem
with applications to lettering of maps. Proceedings of the
7th Annual ACM Symposium on Computational Geometry
281–288.
Hirsch, S. 1982. An algorithm for automatic name placement around point data. The American Cartographer9(1):5–17.