Boundary labeling in text annotation

Chun-Cheng Lin*, Hsiang Yun Wu, Hsu Chun Yen

*Corresponding author for this work

Research output: Contribution to journalConference article

7 Scopus citations


The text annotation system of a word processor software provides the user the function of memorandums in editing a document. In the visualization interface of the annotation system, each marked word is connected to a text comment label on the right side of the document by a polygonal line. Such a visualization interface can be viewed as a one-side boundary labeling, in which each point site is uniquely connected to a label placed on the right side of an enclosing rectangle by a leader, which may be a rectilinear or straight line segment. In the literature, there have existed some applications and some theoretical results for the boundary labeling. In this paper, we investigate the boundary labeling from the application on the annotation system. For this kind of labeling, if the number of labels on the right side is large, the leaders may be drawn too densely to be recognized easily. Therefore, in this paper, we propose a polynomial time algorithm for the so-called 1.5-side boundary labeling for the annotation system, in which, in addition to being connected to the right side directly, leaders can be routed to the left side temporarily and then finally to the right side. In addition, we investigate a problem for two-side boundary labeling (for the annotation system) that was not discussed previously. We show the problem to be NP-complete, and then proposed a heuristic based on the genetic algorithm to solve it. The experimental results reveal that our approach performs well.

Original languageEnglish
Article number5190766
Pages (from-to)110-115
Number of pages6
JournalProceedings of the International Conference on Information Visualisation
StatePublished - 19 Nov 2009
Event2009 13th International Conference on Information Visualisation, IV 2009 - Barcelona, Spain
Duration: 15 Jul 200917 Jul 2009

Fingerprint Dive into the research topics of 'Boundary labeling in text annotation'. Together they form a unique fingerprint.

  • Cite this