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.

1 Introduction 1
1.1 Related work . . . . . . . . . . . . . . . . . . . 2
1.2 Motivation . . . . . . . . . . . . . . . . . . . . 6
1.3 Preliminary . . . . . . . . . . . . . . . . . . . . 6
1.4 Problem Definition . . . . . . . . . . . . . . . . 9
1.5 Our Contribution . . . . . . . . . . . . . . . . . . 10
1.6 Outline . . . . . . . . . . . . . . . . . . . . . . 10
2 NP-completeness of crossing minimization . . . 11
2.1 Uniform labels, fixed ports with two points per leader . 11
2.2 Chapter Summary . . . . . . . . . . . . . . . . . . 17
3 Minimizing total numb er of crossings . 18
3.1 Minimizing total number of crossing by sorting . . . 18
3.1.1 Uniform labels, fixed ports with two points per leader .18
3.1.2 Uniform labels, fixed ports with three points per leader .19
3.2 Minimizing total number of crossing by swapping . . . 20
3.2.1 Uniform labels, fixed ports with two points per leader . 21
3.2.2 Uniform labels, fixed ports with three points per leader . 21
3.3 Crossing-free labeling . . . . . . . . . . . . 23
3.4 Chapter Summary . . . . . . . . . . . . .25
4 Minimizing the total leader length . 26
4.1 Uniform labels, sliding ports, two points per leader . . 26
4.2 A sweep line algorithm . . . . . . . . . . . . .27
4.2.1 Two points per leader with sliding ports . . . . . 28
4.2.2 Three points per leader with sliding ports . . . . . 35
4.3 Chapter Summary . . . . . . . . . . . . . . . 44
5 Implementation . 46
5.1 Two stacks maps of our algorithm . . . . . . . .46
5.1.1 Counties in Taiwan . . . . . . . . . . 46
5.1.2 Counties in Italy . . . . . . . . . . . . 48
5.1.3 Counties in UK . . . . . . . . . . . . .50
5.1.4 Countries in Africa . . . . . . . . . . . . 52
5.1.5 States in USA . . . . . . . . . . . . . 54
5.1.6 Counties in Europe . . . . . . . . . . 55
5.2 Three stacks maps of our algorithm . . . . . . . . . . 57
5.2.1 Counties in Taiwan . . . . . . . . . . . . . . 57
5.2.2 Countries in Africa . . . . . . . . . . 58
5.2.3 Counties in Italy . . . . . . . . . . . . . . . 60
5.2.4 Counties in UK . . . . . . . . . . . . . . . 61
5.2.5 States in USA . . . . . . . . . . . . . . . . . . 62
5.2.6 Countries in Europe . . . . . . . . . . . . . . . . 63
5.3 Chapter summary . . . . . . . . . . . . . . . . 65
6 Conclusion and Future work . 66
6.1 Conclusion . . . . . . . . . . . . . . . . . . . 66
6.2 Future work . . . . . . . . . . . . . . . . . . 68
Bibliography 70

[1] M. Bekos, M. Kaufmann, M. Nollenburg, and A. Symvonis. Boundary labeling with octilinear leaders. Algorithmica, pages 57:436–461, 2010.

[2] M. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. On multi-stack boundary labeling problems. Proc. of the 10th WSEAS International Conference on Computers, Vouliagmeni, Athens, Greece, July 2006.

[3] M. A. Bekos, S. Cornelsen, M. Fink, S. Hong, M. Kaufmann, M. Nollenburg, I. Rutter, and A. Symvonis. Many-to-one boundary labeling with backbones. Graph Drawing 2013, LNCS 8242:244–255, 2013.

[4] M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Multi-stack boundary labeling problems. In FSTTCS, pages 81–92, 2006.

[5] M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Polygon labeling of minimum leader length. pages 15–21, volume 60 of CRPIT, 2006. Proc of the Asian Pacific Symposium on Information Visualization 2006 (APVIS2006).

[6] M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Area-feature boundary labeling. The Computer Journal, 53(6):827–841, 2010.

[7] M. A. Bekos, M. Kaufmann, A. Symvonis, and A. Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. pages 49–59, 2004.

[8] M. Benkert, H. Haverkort, M. Kroll, and M. Nollenburg. Algorithms for multicriteria boundary labeling. Journal of Graph Algorithms and Applications, 13(3):289–317, 2009.

[9] A. Gemsa, J. H. Haunert, and M. Nollenburg. Boundary labeling algorithms for panorama images. In GIS, pages 289–298, 2011.

[10] H. J. Kao, C. C. Lin, and H. C. Yen. Many-to-one boundary labeling. Journal of Graph Algorithms and Applications, pages 319–356, 2008.

[11] M. Kaufmann. On map labeling with leaders. In Efficient Algorithms, pages 290–304, 2009.

[12] P. Kindermann, B. Niedermann, I. Rutter, M. Schaefer, A. Schulz, and A. Wolff. Multi-side boundary labeling. pages 463–474, volume 8037 of Lecture Notes Computer Science., 2014. Proc. 13th International Symposium on Algorithms and Data Structure.(WADS’13).

[13] C. C. Lin. Crossing-free many-to-one boundary labeling with hyperleaders. In Proc. of 3rd IEEE Pacific Visualization Symposium (Pacific Vis.2010), IEEE Press:185–192, 2010.

[14] C. C. Lin, S. H. Poon, S. Takahashi, H. Y. Wu, and H. C. Yen. One-and-a-halfside boundary labeling. In COCOA, pages 387–398, 2011.

[15] C. C. Lin, H. Y. Wu, and H. C. Yen. Boundary labeling in text annotation. pages 110–115, IEEE CS Press, 2009. Proc of 13th International Conference on Information Visualization (IV09).

[16] K. Nakajima, S. Masuda, T. Fujisawa, and T. Kashiwabara. Crossing minimization in linear embeddings of graphs. IEEE Transactions on Computers, pages 124–127, 1990.

[17] M. Nollenburg, V. Polishchuk, and M. Sysikaski. Dynamic one-sided boundary labeling. In GIS, pages 310–319, 2010.

[18] M. Nollenburg and V. P. M. Sysikaski. Dynamic one-sided boundary labeling. 2006.

[19] D. papadopoulos and A Symvonis. Combining traditional map labeling with boundary labeling. In SOFSEM, pages 111–122, 2011.

[20] F. Wagner. Approximate map labeling is in Ω (nlogn). B 93-18, December 1993.

[21] F. Wagner. Approximate map labeling is in Ω (nlogn). Information Processing Letters, pages 161–165, 1994.

[22] F. Wagner and A. Wolf. Map labeling heuristics: Provably good and practically useful. In ACM Press, pages 109–118, 1995.