Document Open Access Logo

On Compact RAC Drawings

Authors Henry Förster , Michael Kaufmann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.53.pdf
  • Filesize: 1.28 MB
  • 21 pages

Document Identifiers

Author Details

Henry Förster
  • Wilhelm-Schickard-Institut für Informatik, University of Tübingen, Germany
Michael Kaufmann
  • Wilhelm-Schickard-Institut für Informatik, University of Tübingen, Germany

Acknowledgements

We thank Patrizio Angelini for useful discussions and proofreading and the anonymous referees of an earlier version for helpful comments.

Cite As Get BibTex

Henry Förster and Michael Kaufmann. On Compact RAC Drawings. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.53

Abstract

We present new bounds for the required area of Right Angle Crossing (RAC) drawings for complete graphs, i.e. drawings where any two crossing edges are perpendicular to each other. First, we improve upon results by Didimo et al. [Walter Didimo et al., 2011] and Di Giacomo et al. [Emilio Di Giacomo et al., 2011] by showing how to compute a RAC drawing with three bends per edge in cubic area. We also show that quadratic area can be achieved when allowing eight bends per edge in general or with three bends per edge for p-partite graphs. As a counterpart, we prove that in general quadratic area is not sufficient for RAC drawings with three bends per edge.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
  • Human-centered computing → Graph drawings
Keywords
  • RAC drawings
  • visualization of dense graphs
  • compact drawings

Metrics

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

References

  1. M. Ajtai, V. Chvátal, M. M. Newborn, and E. Szemerédi. Crossing-free subgraphs. In Theory and practice of combinatorics, volume 60 of North-Holland Math. Stud., pages 9-12. North-Holland, Amsterdam, 1982. Google Scholar
  2. Patrizio Angelini, Michael A. Bekos, Henry Förster, and Michael Kaufmann. On rac drawings of graphs with one bend per edge. Theoretical Computer Science, 2020. URL: https://doi.org/10.1016/j.tcs.2020.04.018.
  3. Patrizio Angelini, Luca Cittadini, Walter Didimo, Fabrizio Frati, Giuseppe Di Battista, Michael Kaufmann, and Antonios Symvonis. On the perspectives opened by right angle crossing drawings. J. Graph Algorithms Appl., 15(1):53-78, 2011. URL: https://doi.org/10.7155/jgaa.00217.
  4. Patrizio Angelini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, and Anna Lubiw. Large angle crossing drawings of planar graphs in subquadratic area. In Alberto Márquez, Pedro Ramos, and Jorge Urrutia, editors, Computational Geometry - XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, volume 7579 of Lecture Notes in Computer Science, pages 200-209. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-34191-5_19.
  5. Evmorfia N. Argyriou, Michael A. Bekos, and Antonios Symvonis. The straight-line RAC drawing problem is np-hard. J. Graph Algorithms Appl., 16(2):569-597, 2012. URL: https://doi.org/10.7155/jgaa.00274.
  6. Karin Arikushi, Radoslav Fulek, Balázs Keszegh, Filip Moric, and Csaba D. Tóth. Graphs that admit right angle crossing drawings. Comput. Geom., 45(4):169-177, 2012. URL: https://doi.org/10.1016/j.comgeo.2011.11.008.
  7. Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. NIC-planar graphs. Discrete Applied Mathematics, 232:23-40, 2017. URL: https://doi.org/10.1016/j.dam.2017.08.015.
  8. Michael A. Bekos, Walter Didimo, Giuseppe Liotta, Saeed Mehrabi, and Fabrizio Montecchiani. On RAC drawings of 1-planar graphs. Theor. Comput. Sci., 689:48-57, 2017. URL: https://doi.org/10.1016/j.tcs.2017.05.039.
  9. Franz J. Brandenburg, Walter Didimo, William S. Evans, Philipp Kindermann, Giuseppe Liotta, and Fabrizio Montecchiani. Recognizing and drawing IC-planar graphs. Theor. Comput. Sci., 636:1-16, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.026.
  10. Steven Chaplick, Fabian Lipp, Alexander Wolff, and Johannes Zink. Compact drawings of 1-planar graphs with right-angle crossings and few bends. Comput. Geom., 84:50-68, 2019. URL: https://doi.org/10.1016/j.comgeo.2019.07.006.
  11. Emilio Di Giacomo, Walter Didimo, Peter Eades, and Giuseppe Liotta. 2-layer right angle crossing drawings. Algorithmica, 68(4):954-997, 2014. URL: https://doi.org/10.1007/s00453-012-9706-7.
  12. Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Henk Meijer. Area, curve complexity, and crossing resolution of non-planar graph drawings. Theory Comput. Syst., 49(3):565-575, 2011. URL: https://doi.org/10.1007/s00224-010-9275-6.
  13. Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. Area requirement of graph drawings with few crossings per edge. Comput. Geom., 46(8):909-916, 2013. URL: https://doi.org/10.1016/j.comgeo.2013.03.001.
  14. Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. Area-thickness trade-offs for straight-line drawings of planar graphs. Comput. J., 60(1):135-142, 2017. URL: https://doi.org/10.1093/comjnl/bxw075.
  15. Walter Didimo, Peter Eades, and Giuseppe Liotta. Drawing graphs with right angle crossings. Theor. Comput. Sci., 412(39):5156-5166, 2011. URL: https://doi.org/10.1016/j.tcs.2011.05.025.
  16. Vida Dujmović, Joachim Gudmundsson, Pat Morin, and Thomas Wolle. Notes on large angle crossing graphs. Chicago J. Theor. Comput. Sci., 2011, 2011. URL: http://cjtcs.cs.uchicago.edu/articles/CATS2010/4/contents.html.
  17. Christian A. Duncan and Michael T. Goodrich. Planar orthogonal and polyline drawing algorithms. In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 223-246. Chapman and Hall/CRC, 2013. Google Scholar
  18. Peter Eades and Giuseppe Liotta. Right angle crossing graphs and 1-planarity. Discrete Applied Mathematics, 161(7-8):961-969, 2013. URL: https://doi.org/10.1016/j.dam.2012.11.019.
  19. Seok-Hee Hong and Hiroshi Nagamochi. Testing full outer-2-planarity in linear time. In Ernst W. Mayr, editor, Graph-Theoretic Concepts in Computer Science - 41st International Workshop, WG 2015, volume 9224 of Lecture Notes in Computer Science, pages 406-421. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-53174-7_29.
  20. Weidong Huang. Using eye tracking to investigate graph layout effects. In Seok-Hee Hong and Kwan-Liu Ma, editors, APVIS 2007, 6th International Asia-Pacific Symposium on Visualization 2007, pages 97-100. IEEE Computer Society, 2007. URL: https://doi.org/10.1109/APVIS.2007.329282.
  21. Weidong Huang, Peter Eades, and Seok-Hee Hong. Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput., 25(4):452-465, 2014. URL: https://doi.org/10.1016/j.jvlc.2014.03.001.
  22. Frank Thomson Leighton. Complexity Issues in VLSI. Foundations of Computing Series. MIT Press, Cambridge, MA, 1983. Google Scholar
  23. János Pach and Géza Tóth. Graphs drawn with few crossings per edge. Combinatorica, 17(3):427-439, 1997. URL: https://doi.org/10.1007/BF01215922.
  24. Helen C. Purchase. Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interacting with Computers, 13(2):147-162, 2000. URL: https://doi.org/10.1016/S0953-5438(00)00032-1.
  25. Helen C. Purchase, David A. Carrington, and Jo-Anne Allder. Empirical evaluation of aesthetics-based graph layout. Empirical Software Engineering, 7(3):233-255, 2002. Google Scholar
  26. Zahed Rahmati and Fatemeh Emami. RAC drawings in subcubic area. Information Processing Letters, 159-160:105945, 2020. URL: https://doi.org/10.1016/j.ipl.2020.105945.
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