Boundary labeling problems appear in many scenarios such as in annotating educational diagrams, system manuals and information visualization. Let $R$ be a rectangle, and consider $n$ points (called sites) inside $R$ and $n$ points on its top and right sides (called labels). In the two-sided boundary labeling, the goal is to connect each site to exactly one label using one-bend axis-parallel polygonal chains (called leaders) such that no two leaders cross and the total length of leaders is minimized. In this talk, we give an $O(n^3\log n)$-time algorithm for this problem, improving the $O(n^8\log n)$-time algorithm of Kindermann et al. (Algorithmica, 76(1):225-258, 2016).

This is a joint work with Prosenjit Bose, Paz Carmi, J. Mark Keil, and Debajyoti Mondal.