Document Open Access Logo

Boundary Labeling for Rectangular Diagrams

Authors Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, Debajyoti Mondal

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.12.pdf
  • Filesize: 0.8 MB
  • 14 pages

Document Identifiers

Author Details

Prosenjit Bose
  • School of Computer Science, Carleton University, Ottawa, Canada
Paz Carmi
  • Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel
J. Mark Keil
  • Department of Computer Science, University of Saskatchewan, Saskatoon, Canada
Saeed Mehrabi
  • School of Computer Science, Carleton University, Ottawa, Canada
Debajyoti Mondal
  • Department of Computer Science, University of Saskatchewan, Saskatoon, Canada

Funding

Research of Prosenjit Bose and Saeed Mehrabi is supported in part by Natural Sciences and Engineering Research Council of Canada (NSERC). Saeed Mehrabi is also supported by a Carleton-Fields postdoctoral fellowship. Debajyoti Mondal is supported in part by Global Water Futures project (GWF) and Natural Sciences and Engineering Research Council of Canada (NSERC).

Cite As Get BibTex

Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, and Debajyoti Mondal. Boundary Labeling for Rectangular Diagrams. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.12

Abstract

Given a set of n points (sites) inside a rectangle R and n points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site to a distinct port while achieving different labeling aesthetics. We examine the scenario when the connecting lines (leaders) are drawn as axis-aligned polylines with few bends, every leader lies strictly inside R, no two leaders cross, and the sum of the lengths of all the leaders is minimized. In a k-sided boundary labeling problem, where 1 <= k <= 4, the label locations are located on the k consecutive sides of R.
In this paper we develop an O(n^3 log n)-time algorithm for 2-sided boundary labeling, where the leaders are restricted to have one bend. This improves the previously best known O(n^8 log n)-time algorithm of Kindermann et al. (Algorithmica, 76(1):225-258, 2016). We show the problem is polynomial-time solvable in more general settings such as when the ports are located on more than two sides of R, in the presence of obstacles, and even when the objective is to minimize the total number of bends. Our results improve the previous algorithms on boundary labeling with obstacles, as well as provide the first polynomial-time algorithms for minimizing the total leader length and number of bends for 3- and 4-sided boundary labeling. These results settle a number of open questions on the boundary labeling problems (Wolff, Handbook of Graph Drawing, Chapter 23, Table 23.1, 2014).

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Computational geometry
Keywords
  • Boundary labeling
  • Dynamic programming
  • Outerstring graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alexander Wolff and Tycho Strijk. The map-labeling bibliography. http://i11www.ira.uka.de/map-labeling/bibliography/. Online; accessed 10 February, 2018.
  2. Lukas Barth, Andreas Gemsa, Benjamin Niedermann, and Martin Nöllenburg. On the readability of boundary labeling. In 23rd International Symposium Graph Drawing and Network Visualization (GD 2015), Los Angeles, CA, USA, pages 515-527, 2015. Google Scholar
  3. Lukas Barth, Benjamin Niedermann, Martin Nöllenburg, and Darren Strash. Temporal map labeling: A new unified framework with experiments. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS), pages 23:1-23:10. ACM, 2016. Google Scholar
  4. Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, and Antonios Symvonis. Many-to-one boundary labeling with backbones. J. Graph Algorithms Appl., 19(3):779-816, 2015. Google Scholar
  5. Michael A. Bekos, Michael Kaufmann, Martin Nöllenburg, and Antonios Symvonis. Boundary labeling with octilinear leaders. Algorithmica, 57(3):436-461, 2010. Google Scholar
  6. Michael A. Bekos, Michael Kaufmann, Antonios Symvonis, and Alexander Wolff. Boundary labeling: Models and efficient algorithms for rectangular maps. Comput. Geom., 36(3):215-236, 2007. Google Scholar
  7. Marc Benkert, Herman J. Haverkort, Moritz Kroll, and Martin Nöllenburg. Algorithms for multi-criteria boundary labeling. J. Graph Algorithms Appl., 13(3):289-317, 2009. Google Scholar
  8. Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi, and Debajyoti Mondal. Boundary labeling for rectangular diagrams. CoRR, abs/1803.10812, 2018. URL: https://arxiv.org/abs/1803.10812.
  9. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, Berlin Heidelberg, 2008. Google Scholar
  10. Srinivas Doddi, Madhav V. Marathe, Andy Mirzaian, Bernard M. E. Moret, and Binhai Zhu. Map labeling and its generalizations. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 148-157, 1997. Google Scholar
  11. Martin Fink and Subhash Suri. Boundary labeling with obstacles. In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), pages 86-92, 2016. Google Scholar
  12. Michael Formann and Frank Wagner. A packing problem with applications to lettering of maps. In Proceedings of the Seventh Annual Symposium on Computational Geometry (SoCG), pages 281-288. ACM, 1991. Google Scholar
  13. Herbert Freeman. An expert system for the automatic placement of names on a geographic map. Inf. Sci., 45(3):367-378, 1988. Google Scholar
  14. GLEAM. http://www.greatlakesmapping.org/. Online; accessed 10 February, 2018.
  15. Stephen A. Hirsch. An algorithm for automatic name placement around point data. The American Cartographer, 9(1):5-17, 1982. Google Scholar
  16. J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle. An algorithm for the maximum weight independent set problem on outerstring graphs. Comput. Geom., 60:19-25, 2017. Google Scholar
  17. Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, and Alexander Wolff. Multi-sided boundary labeling. Algorithmica, 76(1):225-258, 2016. Google Scholar
  18. Benjamin Niedermann, Martin Nöllenburg, and Ignaz Rutter. Radial contour labeling with straight leaders. In 2017 IEEE Pacific Visualization Symposium (PacificVis 2017), Seoul, South Korea, pages 295-304, 2017. Google Scholar
  19. Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski. Dynamic one-sided boundary labeling. In 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS), pages 310-319, 2010. Google Scholar
  20. Alexander Wolff. Graph drawing and cartography. In Roberto Tamassia, editor, Handbook of graph drawing and visualization, chapter 23, pages 697-736. CRC Press, 2014. Google Scholar
  21. Steven Zoraster. The solution of large 0-1 integer programming problems encountered in automated cartography. Operations Research, 38(5):752-759, 1990. Google Scholar
  22. Steven Zoraster. Practical results using simulated annealing for point feature label placement. Cartography and GIS, 24(4):228-238, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact