Abstract
Boundary labeling deals with labeling point of interest in a visually improved way. We assume that the features that we want to label can b e represented by points, line segments or simple close polygons. The features are inscribed in an axis parallel rectangle R with no two features sharing the same x or y-coordinate. Labels are placed at the boundary of the axis parallel rectangle in its 2^n sides where 0 ≤ n ≤ 2. These labels will contain textual information that will describe the features. We want labels that do not overlap and are large enough to be readable. Even simple formulations of this problem are NP-complete. In this thesis, our objective is to minimize the total leader length and the total number of leader crossings. Our main result is a polynomial time algorithm for crossing-free labeling. We use a sweep line algorithm and dynamic programming to meet our objectives. In the algorithm three points will be attached to one horizontal line which runs from the left side of the label to vertically top or bottom of the x−coordinate of the minimum of the three points. Then vertical lines called prong attach each of the point to the horizontal. In theory in order to have a good looking labeling, we make the points to be a multiples of three. Likewise if two points per line are used, we make sure the points are even numbers. If three points are labeled at a time we use three stack at the boundary of R likewise for two points, we use two stacks. We also analyzed the NP completeness of this boundary labeling problem.