Given a rectilinear map consisting of n disjoint line segments, the co
rresponding map labeling problem is to place a maximum width rectangle
at each segment using one of the three natural ways. In a recent pape
r, it is shown that if all segments are horizontal then the problem ca
n be solved in optimal Theta(n log n) time. For the general problem a
factor-2 approximate solution and a Polynomial Time Approximation Sche
me are also proposed. In this paper, we show that the general problem
is polynomially solvable with a nontrivial use of 2SAT and the solutio
n can be even generalized to the case of allowing k natural placements
for each segment, where k is any fixed constant. We believe this tech
nique can be also used to solve other geometric packing problems. (C)
1998 Elsevier Science B.V.