Faster Multi-sided One-Bend Boundary Labelling.

A 1-bend boundary labelling problem consists of an axis-aligned rectangle B, n points (called sites) in the interior, and n points (called ports) on the labels along the boundary of B. The goal is to find a set of n axis-aligned curves (called leaders), each having at most one bend and connecting one site to one port, such that the leaders are pairwise disjoint. A 1-bend boundary labelling problem is k-sided (\(1\le k\le 4\)) if the ports appear on k different sides of B. Kindermann et al. [Algorithmica, 76(1): 225–258, 2016] showed that the 1-bend 4-sided and 3-sided boundary labelling problems can be solved in \(O(n^9)\) and \(O(n^4)\) time, respectively. Bose et al. [SWAT, 12:1–12:14, 2018] improved the former running time to \(O(n^6)\) by reducing the problem to computing maximum independent set in an outerstring graph. In this paper, we improve both previous results by giving new algorithms with running times \(O(n^5)\) and \(O(n^3\log n)\) to solve the 1-bend 4-sided and 3-sided boundary labelling problems, respectively.