Bose, Prosenjit ;
Carmi, Paz ;
Keil, J. Mark ;
Mehrabi, Saeed ;
Mondal, Debajyoti
Boundary Labeling for Rectangular Diagrams
Abstract
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 axisaligned 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 ksided boundary labeling problem, where 1 <= k <= 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 2sided 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):225258, 2016). We show the problem is polynomialtime 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 polynomialtime algorithms for minimizing the total leader length and number of bends for 3 and 4sided 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).
BibTeX  Entry
@InProceedings{bose_et_al:LIPIcs:2018:8838,
author = {Prosenjit Bose and Paz Carmi and J. Mark Keil and Saeed Mehrabi and Debajyoti Mondal},
title = {{Boundary Labeling for Rectangular Diagrams}},
booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
pages = {12:112:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770682},
ISSN = {18688969},
year = {2018},
volume = {101},
editor = {David Eppstein},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8838},
URN = {urn:nbn:de:0030drops88386},
doi = {10.4230/LIPIcs.SWAT.2018.12},
annote = {Keywords: Boundary labeling, Dynamic programming, Outerstring graphs}
}
2018
Keywords: 

Boundary labeling, Dynamic programming, Outerstring graphs 
Seminar: 

16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Issue date: 

2018 
Date of publication: 

2018 