Many-to-One Boundary Labeling

Boundary labeling is an important variant of information visualization which has found many applications in the real world. A conventional boundary labeling scheme connects one site to a unique label placed on the boundary of the drawing. In certain applications of boundary labeling, however, several sites may be required to connect to an identical label in a picture with abundant numbers of sites and labels. In this thesis, we consider the crossing minimization problem for boundary labeling of multi-site connecting to one label, i.e. the problem of finding a leader and label placement, such that the number of total crossings is minimized. We show that the one-sided labeling problem and the two-sided labeling problem for type-opo leaders (rectilinear lines with either zero or two bends) are NP-complete. We also give approximation algorithms and greedy heuristics for the problems. For all the problems in this thesis, we assume that the connecting label port is a fixed port, i.e. the point where each leader is connected to the label is fixed. We also prove that the one-sided labeling problem for type-po leaders (rectilinear lines with either zero or one bend) is NP-complete and give a heuristic algorithm for it. Finally we study the leader length minimization problem for multi-site-to-one-label boundary labeling and present an O(n2log3n) algorithm.1 Introduction 1 2 Preliminaries 6 2.1 The Boundary Labeling Models ………7 2.2 Type of Leader ………8 3 One-Sided, Uniform Label, opo-Leader, Multi-Site to One Label 11 3.1 Crossing Minimization for One-Sided Multi-Site to One Label Boundary Labeling is NP-complete. ………11 3.2 Approximation Algorithm ………15 3.3 At Most Two Sites to One Label………19 4 Two-Sided, Uniform Label, opo-Leader, Multi-Site to One Label 21 4.1 Crossing Minimization for Two-Sided Multi-Site to One Label Boundary Labeling is NP-complete. ………21 4.2 Approximation Algorithm for Two Sides with Equal Labels ………26 4.3 A Greedy Heuristic for Two-Sided Problem ………30 5 One-Sided, Uniform Label, po-Leader, Multi-Site to One Label 32 5.1 Crossing Minimization for One-Sided Multi-Site to One Label Boundary Labeling is NP-complete. ………32 5.2 A Heuristic for One-Sided po-Leader Problem ………33 6 Conclusions and Future Work 37 References ………4