Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the 6th Asia-Pacific Symposium on Visualisation, APVIS 2007
DOI: 10.7155/jgaa.00169
Many-to-One Boundary Labeling
Vol. 12, no. 3, pp. 319-356, 2008. Regular paper.
Abstract In boundary labeling, each point site is uniquely connected to a label placed on the
boundary of an enclosing rectangle by a leader, which may be a rectilinear
or straight line segment. To our knowledge, all the results reported
in the literature for boundary labeling deal with the so-called
one-to-one boundary labeling, i.e., different sites are labelled
differently. In certain applications of boundary labeling, however,
more than one site may be required to be connected to a common
label. In this case, the presence of crossings among leaders often
becomes inevitable. Minimizing the total number of crossings in
boundary labeling becomes a critical design issue as crossing is
often regarded as the main source of confusion in visualization.
In this paper, we consider the crossing
minimization problem for multi-site-to-one-label boundary
labeling, i.e., finding the placements of labels and leaders such
that the total number of crossings among leaders is minimized.
We show the crossing minimization problem to be NP-complete under
certain
one-side and two-side labeling schemes.
Subsequently, approximation algorithms or heuristics are derived
for the above intractable problems.
|
Submitted: June 2007.
Reviewed: September 2007.
Revised: February 2008.
Accepted: April 2008.
Final: August 2008.
Published: October 2008.
Communicated by
Seok-Hee Hong
|
Journal Supporters
|