Polyline Drawings with Topological Constraints

Authors Emilio Di Giacomo , Peter Eades, Giuseppe Liotta , Henk Meijer, Fabrizio Montecchiani



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.39.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Emilio Di Giacomo
  • Università degli Studi di Perugia, Perugia, Italy
Peter Eades
  • University of Sydney, Sydney, Australia
Giuseppe Liotta
  • Università degli Studi di Perugia, Perugia, Italy
Henk Meijer
  • University College Roosevelt, Middelburg, The Netherlands
Fabrizio Montecchiani
  • Università degli Studi di Perugia, Perugia, Italy

Cite AsGet BibTex

Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani. Polyline Drawings with Topological Constraints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.39

Abstract

Let G be a simple topological graph and let Gamma be a polyline drawing of G. We say that Gamma partially preserves the topology of G if it has the same external boundary, the same rotation system, and the same set of crossings as G. Drawing Gamma fully preserves the topology of G if the planarization of G and the planarization of Gamma have the same planar embedding. We show that if the set of crossing-free edges of G forms a connected spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Omega(sqrt{n}). Concerning drawings that fully preserve the topology, we show that if G has skewness k, it admits one such drawing with curve complexity at most 2k; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs and discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Graph theory
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Topological graphs
  • graph drawing
  • curve complexity
  • skewness-k graphs
  • k-planar graphs

Metrics

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

References

  1. Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Thomas Hackl, Jürgen Pammer, Alexander Pilz, Pedro Ramos, Gelasio Salazar, and Birgit Vogtenhuber. All Good Drawings of Small Complete Graphs. In EuroCG 2015, pages 57-60, 2015. Google Scholar
  2. Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Gelasio Salazar, and Birgit Vogtenhuber. Deciding monotonicity of good drawings of the complete graph. In EGC 2015, pages 33-36, 2015. Google Scholar
  3. David W. Barnette. 2-Connected Spanning Subgraphs of Planar 3-Connected Graphs. J. Combin. Theory Ser. B, 61(2):210-216, 1994. Google Scholar
  4. Michael A. Bekos, Michael Kaufmann, and Fabrizio Montecchiani. Guest Editors' Foreword and Overview. J. Graph Algorithms Appl., 22(1):1-10, 2018. Google Scholar
  5. Michael A. Bekos, Michael Kaufmann, and Chrysanthi N. Raftopoulou. On Optimal 2- and 3-Planar Graphs. In SOCG 2017, volume 77 of LIPIcs, pages 16:1-16:16. LZI, 2017. Google Scholar
  6. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. 1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area. In GD 2018. Springer, To appear. Google Scholar
  7. Norishige Chiba, Kazunori Onoguchi, and Takao Nishizeki. Drawing plane graphs nicely. Acta Inform., 22(2):187-201, 1985. Google Scholar
  8. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A Survey on Graph Drawing Beyond Planarity. CoRR, abs/1804.07257, 2018. URL: http://arxiv.org/abs/1804.07257.
  9. Stephane Durocher and Debajyoti Mondal. Relating Graph Thickness to Planar Layers and Bend Complexity. In ICALP 2016, volume 55 of LIPIcs, pages 10:1-10:13. LZI, 2016. Google Scholar
  10. Peter Eades, Seok-Hee Hong, Giuseppe Liotta, Naoki Katoh, and Sheung-Hung Poon. Straight-Line Drawability of a Planar Graph Plus an Edge. In WADS 2015, pages 301-313. Springer, 2015. Google Scholar
  11. David Eppstein, Mereke van Garderen, Bettina Speckmann, and Torsten Ueckerdt. Convex-Arc Drawings of Pseudolines. CoRR, abs/1601.06865, 2016. URL: http://arxiv.org/abs/1601.06865.
  12. István Fáry. On straight line representations of planar graphs. Acta Univ. Szeged. Sect. Sci. Math., 11:229-233, 1948. Google Scholar
  13. Emilio Di Giacomo, Petere Eades, Giuseppe Liotta, Henk Meijer, and Fabrizio Montecchiani. Polyline Drawings with Topological Constraints. CoRR, abs/1809.08111, 2018. URL: http://arxiv.org/abs/1809.08111.
  14. Jan Kratochvíl, Anna Lubiw, and Jaroslav Nešetřil. Noncrossing Subgraphs in Topological Layouts. SIAM J. Discrete Math., 4(2):223-244, 1991. Google Scholar
  15. Jan Kynčl. Simple Realizability of Complete Abstract Topological Graphs in P. Discrete Comput. Geom., 45(3):383-399, 2011. Google Scholar
  16. Jan Kynčl. Enumeration of simple complete topological graphs. European Journal of Combinatorics, 30(7):1676-1685, 2009. Google Scholar
  17. Sherman K. Stein. Convex maps. Proc. Am. Math. Soc., 2(3):464-466, 1951. Google Scholar
  18. Klaus Wagner. Bemerkungen zum Vierfarbenproblem. Jahresber. Dtsch. Math. Ver., 46:26-32, 1936. 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