Multi-sided boundary labeling

DOI10.1007/S00453-015-0028-4zbMATH Open1348.68283arXiv1305.0750OpenAlexW3102064085MaRDI QIDQ334944FDOQ334944

Authors: Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, Alexander Wolff 

Publication date: 1 November 2016

Published in: Algorithmica (Search for Journal in Brave)

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 Multi-Sided Boundary Labeling problem, with labels lying on at least two 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 in which labels lie on one side or on two opposite sides of $R$ (here a crossing-free 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 crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.

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

Recommendations

• Two-sided boundary labeling with adjacent sides
• Boundary labeling for rectangular diagrams
• Many-to-One Boundary Labeling
• Boundary labeling: Models and efficient algorithms for rectangular maps
• Algorithms for Multi-Criteria Boundary Labeling

zbMATH Keywords

computational geometryboundary labelingdynamic program

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
• A linear space algorithm for computing maximal common subsequences
• Point labeling with sliding labels
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
• Algorithms for Multi-Criteria Boundary Labeling
• Manhattan-geodesic embedding of planar graphs
• Single bend wiring
• Disjoint Paths in the Plane
• Many-to-One Boundary Labeling
• Many-to-One Boundary Labeling with Backbones
• Boundary labeling: Models and efficient algorithms for rectangular maps
• Boundary labeling with octilinear leaders

Cited In (12)

• Algorithms for Multi-criteria One-Sided Boundary Labeling
• One-and-a-half-side boundary labeling
• Labeling nonograms: boundary labeling for curve arrangements
• Planar drawings of fixed-mobile bigraphs
• Faster multi-sided one-bend boundary labelling
• Algorithms for Multi-Criteria Boundary Labeling
• Boundary Labeling for Rectangular Diagrams
• Boundary Labeling with Octilinear Leaders
• Many-to-One Boundary Labeling
• Boundary labeling with octilinear leaders
• Efficient Labeling of Collinear Sites
• Multi-stack Boundary Labeling Problems

This page was built for publication: Multi-sided boundary labeling

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