Boundary Labeling

Two-Sided Boundary Labeling with Adjacent Sides

Philipp Kindermann1 , Benjamin Niedermann2 , Ignaz Rutter2 , Marcus Schaefer3 , André Schulz4 , and Alexander Wolff1

Lehrstuhl für Informatik I, Universität Würzburg, Germany. http://www1.informatik.uni-wuerzburg.de/en/staff 2 Fakultät für Informatik, Karlsruher Institut für Technologie (KIT), Germany. {benjamin.niedermann,rutter}@kit.edu 3 College of Computing and Digital Media, DePaul University, Chicago, IL, USA. mschaefer@cs.depaul.edu Institut für Mathematische Logik und Grundlagenforschung, Universität Münster, Germany. andre.schulz@uni-muenster.de

1

4

Abstract. In the Boundary Labeling problem, we are given a set of n points, referred to as sites, inside an axis-parallel 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 non-intersecting rectilinear paths, so-called leaders, with at most one bend. In this paper, we study the problem Two-Sided Boundary Labeling with Adjacent Sides, where labels lie on two adjacent sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases that labels lie on one side or on two opposite sides of R (where a crossing-free solution always exists). For the more difficult case where labels lie on adjacent sides, we show how to compute crossing-free leader layouts that maximize the number of labeled points or minimize the total leader length.

1 Introduction

Label placement is an important problem in cartography and, more generally, information visualization. Features such as points, lines, and regions in maps, diagrams, and technical drawings often have to be labeled so that users understand better what they see. Even very restricted versions of the label-placement problem are NP-hard [14], which explains why labeling a map manually is a...