Authors: Philipp Kindermann Benjamin Niedermann Ignaz Rutter Marcus Schaefer André Schulz Alexander Wolff
Publish Date: 2015/07/21
Volume: 76, Issue: 1, Pages: 225-258
Abstract
In the Boundary Labeling problem we are given a set of n points referred to as sites inside an axisparallel rectangle R and a set of n pairwise disjoint rectangular labels that are attached to R from the outside The task is to connect the sites to the labels by nonintersecting rectilinear paths socalled leaders with at most one bend In this paper we study the MultiSided Boundary Labeling problem with labels lying on at least two sides of the enclosing rectangle We present a polynomialtime algorithm that computes a crossingfree leader layout if one exists So far such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of R here a crossingfree solution always exists The case where labels may lie on adjacent sides is more difficult We present efficient algorithms for testing the existence of a crossingfree leader layout that labels all sites and also for maximizing the number of labeled sites in a crossingfree leader layout For twosided boundary labeling with adjacent sides we further show how to minimize the total leader length in a crossingfree layoutA preliminary version of this paper has appeared in Proc 13th Int Algorithms Data Struct Symp WADS’13 volume 8037 of Lect Notes Comput Sci pages 463–474 SpringerVerlag This research was initiated during the GraDr Midterm meeting at the TU Berlin in October 2012 The meeting was supported by the ESF EuroGIGA networking grant Ph Kindermann acknowledges support by the ESF EuroGIGA project GraDR DFG Grant Wo 758/51
Keywords: