Document Open Access Logo

RAC Drawings of Graphs with Low Degree

Authors Patrizio Angelini , Michael A. Bekos , Julia Katheder , Michael Kaufmann , Maximilian Pfister

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.11.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Patrizio Angelini
  • John Cabot University, Rome, Italy
Michael A. Bekos
  • Department of Mathematics, University of Ioannina, Ioannina, Greece
Julia Katheder
  • Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Tübingen, Germany
Michael Kaufmann
  • Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Tübingen, Germany
Maximilian Pfister
  • Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Tübingen, Germany

Cite AsGet BibTex

Patrizio Angelini, Michael A. Bekos, Julia Katheder, Michael Kaufmann, and Maximilian Pfister. RAC Drawings of Graphs with Low Degree. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.11

Abstract

Motivated by cognitive experiments providing evidence that large crossing-angles do not impair the readability of a graph drawing, RAC (Right Angle Crossing) drawings were introduced to address the problem of producing readable representations of non-planar graphs by supporting the optimal case in which all crossings form 90° angles. In this work, we make progress on the problem of finding RAC drawings of graphs of low degree. In this context, a long-standing open question asks whether all degree-3 graphs admit straight-line RAC drawings. This question has been positively answered for the Hamiltonian degree-3 graphs. We improve on this result by extending to the class of 3-edge-colorable degree-3 graphs. When each edge is allowed to have one bend, we prove that degree-4 graphs admit such RAC drawings, a result which was previously known only for degree-3 graphs. Finally, we show that 7-edge-colorable degree-7 graphs admit RAC drawings with two bends per edge. This improves over the previous result on degree-6 graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph Drawing
  • RAC graphs
  • Straight-line and bent drawings

Metrics

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

Related Versions

References

  1. Patrizio Angelini, Michael A. Bekos, Henry Förster, and Michael Kaufmann. On RAC drawings of graphs with one bend per edge. Theor. Comput. Sci., 828-829:42-54, 2020. URL: https://doi.org/10.1016/j.tcs.2020.04.018.
  2. Patrizio Angelini, Michael A. Bekos, Julia Katheder, Michael Kaufmann, and Maximilian Pfister. RAC drawings of graphs with low degree. CoRR, abs/2206.14909, 2022. URL: http://arxiv.org/abs/2206.14909.
  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. Evmorfia N. Argyriou, Michael A. Bekos, Michael Kaufmann, and Antonios Symvonis. Geometric RAC simultaneous drawings of graphs. J. Graph Algorithms Appl., 17(1):11-34, 2013. URL: https://doi.org/10.7155/jgaa.00282.
  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. 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.
  8. 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.
  9. Norishige Chiba, Kazunori Onoguchi, and Takao Nishizeki. Drawing planar graphs nicely. Acta Inform., 22:187-201, 1985. URL: https://doi.org/10.1007/BF00264230.
  10. Marek Chrobak and Thomas H. Payne. A linear-time algorithm for drawing a planar graph on a grid. Inf. Process. Lett., 54(4):241-246, 1995. URL: https://doi.org/10.1016/0020-0190(95)00020-D.
  11. Hubert de Fraysseix, János Pach, and Richard Pollack. Small sets supporting Fáry embeddings of planar graphs. In Janos Simon, editor, Symposium on the Theory of Computing, pages 426-433. ACM, 1988. URL: https://doi.org/10.1145/62212.62254.
  12. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. Google Scholar
  13. 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.
  14. Walter Didimo. Right angle crossing drawings of graphs. In Seok-Hee Hong and Takeshi Tokuyama, editors, Beyond Planar Graphs, pages 149-169. Springer, 2020. URL: https://doi.org/10.1007/978-981-15-6533-5_9.
  15. Walter Didimo, Peter Eades, and Giuseppe Liotta. Drawing graphs with right angle crossings. In Frank K. H. A. Dehne, Marina L. Gavrilova, Jörg-Rüdiger Sack, and Csaba D. Tóth, editors, Workshop on Algorithms and Data Structures, volume 5664 of LNCS, pages 206-217. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-03367-4_19.
  16. Walter Didimo, Peter Eades, and Giuseppe Liotta. A characterization of complete bipartite RAC graphs. Inf. Process. Lett., 110(16):687-691, 2010. URL: https://doi.org/10.1016/j.ipl.2010.05.023.
  17. 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.
  18. Walter Didimo and Giuseppe Liotta. The crossing-angle resolution in graph drawing. In János Pach, editor, Thirty Essays on Geometric Graph Theory, pages 167-184. Springer, 2013. Google Scholar
  19. Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv., 52(1):4:1-4:37, 2019. URL: https://doi.org/10.1145/3301281.
  20. Peter Eades, Antonios Symvonis, and Sue Whitesides. Three-dimensional orthogonal graph drawing algorithms. Discret. Appl. Math., 103(1-3):55-87, 2000. URL: https://doi.org/10.1016/S0166-218X(00)00172-4.
  21. Henry Förster and Michael Kaufmann. On compact RAC drawings. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, European Symposium on Algorithms, volume 173 of LIPIcs, pages 53:1-53:21. Schloss Dagstuhl, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.53.
  22. István Fáry. On straight lines representation of planar graphs. Acta Sci. Math. (Szeged), 11:229-233, 1948. Google Scholar
  23. M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic Discrete Methods, 4(3):312-316, 1983. URL: https://doi.org/10.1137/0604033.
  24. Ian Holyer. The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718-720, 1981. URL: https://doi.org/10.1137/0210055.
  25. Seok-Hee Hong and Takeshi Tokuyama, editors. Beyond Planar Graphs. Springer, 2020. URL: https://doi.org/10.1007/978-981-15-6533-5.
  26. 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.
  27. Julius Petersen. Die Theorie der regulären graphs. Acta Mathematica, 15:193-220, 1891. URL: https://doi.org/10.1007/BF02392606.
  28. Helen C. Purchase. Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interact. Comput., 13(2):147-162, 2000. URL: https://doi.org/10.1016/S0953-5438(00)00032-1.
  29. Marcus Schaefer. Rac-drawability is ∃ R-Complete. In Helen C. Purchase and Ignaz Rutter, editors, Graph Drawing and Network Visualization, volume 12868 of LNCS, pages 72-86. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-92931-2_5.
  30. Sherman K. Stein. Convex maps. Proc. American Math. Soc., 2(3):464-466, 1951. Google Scholar
  31. E. Steinitz and H. Rademacher. Vorlesungen über die Theorie der Polyeder. Julius Springer, Berlin, Germany, 1934. Google Scholar
  32. Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987. URL: https://doi.org/10.1137/0216030.
  33. William Thomas Tutte. How to draw a graph. Proc. London Math. Soc., 13:743-768, 1963. Google Scholar
  34. Klaus Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung, 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact