Elastic Labels: The TwoAxis CaseIturriaga, Claudia and Lubiw, Anna (1998) Elastic Labels: The TwoAxis Case. In: Graph Drawing 5th International Symposium, GD '97, September 1820, 1997 , pp. 181192(Official URL: http://dx.doi.org/10.1007/3540639381_61). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540639381_61
AbstractOne of the most challenging tasks of cartographic map lettering is the optimal placement of region information on a map. We propose as an approach to this task the elastic labeling problem, in which we are given a set of elastic rectangles as labels, each associated with a point in the plane. An elastic rectangle has a specified area but its width and high may vary. The problem then is to choose the height and width of each label, and the corner of the label to place at the associated point, so that no two labels overlap. This problem is known to be NPhard even when there is no elasticity (just because of the choice of the corners). We show that the problem remains NPhard when we have elasticity but no choice about which corner of the label to use  we call this the onecorner elastic labeling problem. We give a polynomial time algorithm for the special case of the onecorner elastic labeling problem in which the points lie on the positive x and y axes and the lables lie in the first quadrant. We call this the twoaxis labeling problem.
Actions (login required)
