  Given a set of $n$ points (sites) inside a rectangle $R$ and $n$ points
(label locations or ports) on its boundary, a boundary labeling problem seeks
ways of connecting every site to a distinct port while achieving different
labeling aesthetics. We examine the scenario when the connecting lines
(leaders) are drawn as axis-aligned polylines with few bends, every leader lies
strictly inside $R$, no two leaders cross, and the sum of the lengths of all
the leaders is minimized. In a $k$-sided boundary labeling problem, where $1\le
k\le 4$, the label locations are located on the $k$ consecutive sides of $R$.
  In this paper, we develop an $O(n^3\log n)$-time algorithm for 2-sided
boundary labeling, where the leaders are restricted to have one bend. This
improves the previously best known $O(n^8\log n)$-time algorithm of Kindermann
et al. (Algorithmica, 76(1):225-258, 2016). We show the problem is
polynomial-time solvable in more general settings such as when the ports are
located on more than two sides of $R$, in the presence of obstacles, and even
when the objective is to minimize the total number of bends. Our results
improve the previous algorithms on boundary labeling with obstacles, as well as
provide the first polynomial-time algorithms for minimizing the total leader
length and number of bends for 3- and 4-sided boundary labeling. These results
settle a number of open questions on the boundary labeling problems (Wolff,
Handbook of Graph Drawing, Chapter 23, Table 23.1, 2014).
