Map Labeling Problems

selected by Yu-Shin Chen

Reference link :

http://i11www.ira.uka.de/map-labeling/

Paper selection :

Map labeling problem survey

    - NP-hardness of some map labeling problems(1997)     

                Claudia Iturriaga & AnnaLubiw                                                             pdf-->

    - Rectangle intersection AND overlap graphs(1995)

             Chong S. Rim and Kazup Nakajima                                                      pdf-->

Circle label

    - Labeling points with circles  (1999)

            T. Strijk and A. Wolff                                                                               pdf-->          

    - A new bound for map labeling with uniform

      circle pairs (2000)

            Michael J. Spriggs, J. Mark Keil                                                         pdf-->                

    - A simple factor-2_3 approximation algorithm for

      two-circle point labeling (2001)

          ALEXANDER WOLFF, MICHAEL THON, YINFENG XU              pdf-->            

    - A better lower-bound   

            ALEXANDER WOLFF, MICHAEL THON, YINFENG XU              pdf-->

Rectilinear label

    2-label on points

            - Efficient approximation algorithms for two-label point labeling(2000)

            Binhai Zhu and Chung Keung Poon                                                                            pdf-->

        3-label on points

         - Polynomial Time Algorithms for Three-label Point Labeling (2001)  

            Duncan, Qian, Vigneron, Zhu                                                                                      pdf-->

        elastic-label on points

            - Elastic Labels Around the Perimeter of a Map(2001) 

                 Claudia Iturriaga, Anna Lubiw's                                                                                   pdf-->

         - Elastic Labels on the Perimeter of a Rectangle(1998)   

               Claudia Iturriaga, Anna Lubiw                                                                                        pdf-->

         - Elastic Labels- The Two-axis Case(1997)

                 Claudia Iturriaga, Anna Lubiw                                                                                      pdf-->

        sliding label

         - Labeling a rectilinear map with sliding labels(1999)

                Sung Kwon Kim, Chan-Su Shin, Tae-Cheon Yang                                                        pdf-->

         - Point set labeling with sliding labels(1998)   

                 Marc J. van Kreveld, Tycho Strijk, and Alexander Wolff                                              pdf-->

        labeling on rectilinear map

            - A polynomial time solution for labeling a rectilinear map(1998)

                Chung Keung Poon, Binhai Zhu, and Francis Chin                                                        pdf-->

         - Labeling a rectilinear map more efficiently(1999)

                Tycho Strijk and Marc van Kreveld                                                                                pdf-->

        others

         - A combinatorial framework for map labeling(1998)

                FRANK WAGNER, ALEXANDER WOLFF                                                                                                    pdf-->

         - A packing problem with applications to lettering of maps(1991)

                Michael Formann , Frank Wagner                                                                                 pdf-->

         - A Practical Map Labeling Algorithm(1997)

                 FRANK WAGNER, ALEXANDER WOLFF                                                                                                   ps-->

         - Labeling Heuristics for Orthogonal Drawings(2001)

                 Carla Binucci, Walter Didimo, Giuseppe Liotta, Maddalena Nonato                            pdf-->

         - Labeling points with rectangles of various shapes(2000)

                  Shin-ichi Nakano, Takao Nishizeki, Takeshi Tokuyama, Shuhei Watanabe                pdf-->

         - Labeling subway lines(2001)

                 Mari Ángeles Garrido, Claudia Iturriaga, Alberto Márquez, José Ramón Portillo, Pedro Reyes, Alexander   Wolff                                                                                                                                                          pdf-->

Others

    - A Unified Approach to Labeling Graphical Features(1998)               

             Konstantinos G. Kakoulis and Ioannis G. Tollis                                                                  pdf-->

    - An Algorithm for Labeling Edges of Hierarchical Drawings(1998)

            Konstantinos G. Kakoulis and Ioannis G. Tollis                                                                  pdf-->