Boundary Labeling for Rectangular Diagrams

DOI10.4230/LIPICS.SWAT.2018.12zbMATH Open1477.68461arXiv1803.10812OpenAlexW2963350132MaRDI QIDQ5116476FDOQ5116476

Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, Debajyoti Mondal

Publication date: 25 August 2020

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 axis-aligned 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 $k$-sided boundary labeling problem, where $1lekle4$, the label locations are located on the $k$ consecutive sides of $R$. In this paper, we develop an $O(n^{3}logn)$-time algorithm for 2-sided boundary labeling, where the leaders are restricted to have one bend. This improves the previously best known $O(n^{8}logn)$-time algorithm of Kindermann et al. (Algorithmica, 76(1):225-258, 2016). We show the problem is polynomial-time 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 polynomial-time algorithms for minimizing the total leader length and number of bends for 3- and 4-sided 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).

Full work available at URL: https://arxiv.org/abs/1803.10812

zbMATH Keywords

dynamic programmingboundary labelingouterstring graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Dynamic programming (90C39) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Multi-sided boundary labeling
• Algorithms for Multi-Criteria Boundary Labeling
• Boundary labeling: Models and efficient algorithms for rectangular maps
• Boundary labeling with octilinear leaders
• An algorithm for the maximum weight independent set problem on outerstring graphs
• On the Readability of Boundary Labeling
• Many-to-One Boundary Labeling with Backbones

Cited In (3)

• Faster multi-sided one-bend boundary labelling
• Labelings for Decreasing Diagrams.
• Labeling points with given rectangles

This page was built for publication: Boundary Labeling for Rectangular Diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116476)