One-and-a-half-side boundary labeling

Chun-Cheng Lin*, Sheung Hung Poon, Shigeo Takahashi, Hsiang Yun Wu, Hsu Chun Yen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


In boundary labeling, each point site in a rectangular map is connected to a label outside the map by a leader, which may be a rectilinear or a straight-line segment. Among various types of leaders, the so-called type-opo leader consists of three segments (from the site to its associated label) that are orthogonal, then parallel, and then orthogonal to the side to which the label is attached. In this paper, we investigate the so-called 1.5-side boundary labeling, in which, in addition to being connected to the right side of the map directly, type-opo leaders can be routed to the left side temporarily and then finally to the right side. It turns out that allowing type-opo leaders to utilize the left side of a map is beneficial in the sense that it produces a better labeling result in some cases. To understand this new version of boundary labeling better, we investigate from a computational complexity viewpoint the total leader length minimization problem as well as the bend minimization problem for variants of 1.5-side boundary labeling, which are parameterized by the underlying label size (uniform vs. nonuniform) and port type (fixed-ratio, fixed-position, vs. sliding). For the case of nonuniform labels, the above two problems are intractable in general. We are able to devise pseudo-polynomial time solutions for such intractable problems, and also identify the role played by the number of distinct labels in the overall complexity. On the other hand, if labels are identical in size, both problems become solvable in polynomial time. We also characterize the cases for which utilizing the left side for routing type-opo leaders does not help.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
Number of pages12
StatePublished - 2011
Event5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011 - Zhangjiajie, China
Duration: 4 Aug 20116 Aug 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6831 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011


  • Map labeling
  • boundary labeling
  • complexity


Dive into the research topics of 'One-and-a-half-side boundary labeling'. Together they form a unique fingerprint.

Cite this