Paper Info
Title
Labeling Subway Lines
Abstract
Graphical features on map, charts, diagrams and graph draw- ings usually must be annotated with text labels in order to convey their meaning. In this paper we focus on a problem that arises when labeling schematized maps, e.g. for subway networks. We present algorithms for labeling points on a line with axis-parallel rectangular labels of equal height. Our aim is to maximize label size under the constraint that all points must be labeled. Even a seemingly strong simplification of the general point-labeling prob- lem, namely to decide whether a set of points on a horizontal line can be labeled with sliding rectangular labels, turns out to be weakly NP- complete. This is the first labeling problem that is known to belong to this class. We give a pseudo-polynomial time algorithm for it. In case of a sloping line points can be labeled with maximum-size square labels in O(nlog n) time if four label positions per point are allowed and in O(n3 log n) time if labels can slide. We also investigate rectangular labels.
Year
DOI
Venue
2001
10.1007/3-540-45678-3_55
International Symposium on Algorithms and Computation
Keywords
Field
DocType
label position,axis-parallel rectangular label,sloping line point,horizontal line,rectangular label,subway lines,label size,n log n,n3 log n,general point-labeling problem,pseudo-polynomial time algorithm,generic point,graph drawing
Graph,Binary logarithm,Discrete mathematics,Combinatorics,Computer science,Computer communication networks,Computational geometry,Time complexity,Horizontal line test,Distributed computing,Theory of computation,Labeling Problem
Conference
Volume
ISSN
ISBN
2223
0302-9743
3-540-42985-9
Citations 
PageRank 
References 
12
0.87
12
Authors
6
Name
Order
Citations
PageRank
Maria Angeles Garrido1121.55
Claudia Iturriaga2353.60
Alberto Márquez312420.06
José Ramón Portillo4121.21
Pedro Reyes5191.40
Alexander Wolff622222.66