TY - GEN
T1 - Boundary labeling with flexible label positions
AU - Huang, Zhi Dong
AU - Poon, Sheung Hung
AU - Lin, Chun Cheng
N1 - Funding Information:
Supported in part by grants 97-2221-E-007-054-MY3 and 100-2628-E-007-020-MY3 of the National Science Council (NSC), Taiwan, R.O.C.
PY - 2014
Y1 - 2014
N2 - Boundary labeling connects each point site in a rectangular map to a label on the sides of the map by a leader, which may be a straight-line segment or a polyline. In the conventional setting, the labels along a side of the map form a single stack of labels in which labels are placed consecutively one by one in a sequence, and the two end sides of a label stack must respect the sides of the map. However, such a setting may be in conflict with generation of a better boundary labeling, measured by the total leader length or the number of bends of leaders. As a result, this paper relaxes this setting to propose the boundary labeling with flexible label positions, in which labels are allowed to be placed at any non-overlapping location along the sides of the map so that they do not necessarily form only one single stack, and the two end sides of label stacks do not need to respect the sides of the map. In this scenario, we investigate the total leader length minimization problem and the total bend minimization problem under several variants, which are parameterized by the number of sides to which labels are attached, their label size, port types, and leader types. It turns out that almost all of the total leader length minimization problems using nonuniform-size labels are NP-complete except for one case, while the others can be solved in polynomial time.
AB - Boundary labeling connects each point site in a rectangular map to a label on the sides of the map by a leader, which may be a straight-line segment or a polyline. In the conventional setting, the labels along a side of the map form a single stack of labels in which labels are placed consecutively one by one in a sequence, and the two end sides of a label stack must respect the sides of the map. However, such a setting may be in conflict with generation of a better boundary labeling, measured by the total leader length or the number of bends of leaders. As a result, this paper relaxes this setting to propose the boundary labeling with flexible label positions, in which labels are allowed to be placed at any non-overlapping location along the sides of the map so that they do not necessarily form only one single stack, and the two end sides of label stacks do not need to respect the sides of the map. In this scenario, we investigate the total leader length minimization problem and the total bend minimization problem under several variants, which are parameterized by the number of sides to which labels are attached, their label size, port types, and leader types. It turns out that almost all of the total leader length minimization problems using nonuniform-size labels are NP-complete except for one case, while the others can be solved in polynomial time.
UR - http://www.scopus.com/inward/record.url?scp=84958553567&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-04657-0_7
DO - 10.1007/978-3-319-04657-0_7
M3 - Conference contribution
AN - SCOPUS:84958553567
SN - 9783319046563
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 44
EP - 55
BT - Algorithms and Computation - 8th International Workshop, WALCOM 2014, Proceedings
PB - Springer Verlag
T2 - 8th International Workshop on Algorithms and Computation, WALCOM 2014
Y2 - 13 February 2014 through 15 February 2014
ER -