Document Open Access Logo

Drawing Graphs with Circular Arcs and Right-Angle Crossings

Authors Steven Chaplick , Henry Förster , Myroslav Kryven, Alexander Wolff

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.21.pdf
  • Filesize: 0.93 MB
  • 14 pages

Document Identifiers

Author Details

Steven Chaplick
  • Maastricht University, the Netherlands
  • University of Würzburg, Germany
Henry Förster
  • University of Tübingen, Germany
Myroslav Kryven
  • University of Würzburg, Germany
Alexander Wolff
  • University of Würzburg, Germany

Funding

  • Kryven, Myroslav: M. Kryven acknowledges support from DFG grant WO 758/9-1.

Acknowledgements

We thank the reviewers of our paper for their very detailed comments, which helped us to improve the writing a lot.

Cite As Get BibTex

Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. Drawing Graphs with Circular Arcs and Right-Angle Crossings. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.21

Abstract

In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n-10 edges.
We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n-12 edges and that there are n-vertex arc-RAC graphs with 4.5n - O(√n) edges.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graphs and surfaces
  • Mathematics of computing → Combinatoric problems
Keywords
  • circular arcs
  • right-angle crossings
  • edge density
  • charging argument

Metrics

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

References

  1. Eyal Ackerman. On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom., 41(3):365-375, 2009. URL: https://doi.org/10.1007/s00454-009-9143-9.
  2. Eyal Ackerman and Gábor Tardos. On the maximum number of edges in quasi-planar graphs. J. Combin. Theory, Ser. A, 114(3):563-571, 2007. URL: https://doi.org/10.1016/j.jcta.2006.08.002.
  3. Oswin Aichholzer, Wolfgang Aigner, Franz Aurenhammer, Kateřina Čech Dobiášová, Bert Jüttler, and Günter Rote. Triangulations with circular arcs. In Marc van Kreveld and Bettina Speckmann, editors, Proc. Graph Drawing (GD'11), volume 7034 of LNCS, pages 296-307. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-25878-7_29.
  4. Patrizio Angelini, Michael A. Bekos, Henry Förster, and Michael Kaufmann. On RAC drawings of graphs with one bend per edge. In Therese Biedl and Andreas Kerren, editors, Proc. Graph Drawing & Network Vis. (GD'18), volume 11282 of LNCS, pages 123-136. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-04414-5_9.
  5. Karin Arikushi, Radoslav Fulek, Baláazs Keszegh, Filip Morić, 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.
  6. Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. NIC-planar graphs. Discrete Appl. Math., 232:23-40, 2017. URL: https://doi.org/10.1016/j.dam.2017.08.015.
  7. Michael A. Bekos, Walter Didimo, Giuseppe Liotta, Saeed Mehrabi, and Fabrizio Montecchiani. On RAC drawings of 1-planar graphs. Theoretical Comput. Sci., 689:48-57, 2017. URL: https://doi.org/10.1016/j.tcs.2017.05.039.
  8. Franz J. Brandenburg, Walter Didimo, William S. Evans, Philipp Kindermann, Giuseppe Liotta, and Fabrizio Montecchiani. Recognizing and drawing IC-planar graphs. Theoret. Comput. Sci., 636:1-16, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.026.
  9. Steven Chaplick, Henry Förster, Myroslav Kryven, and Alexander Wolff. On arrangements of orthogonal circles. In Daniel Archambault and Csaba D. Tóth, editors, Proc. Graph Drawing and Network Visualization (GD'19), volume 11904 of LNCS, pages 216-229. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-35802-0_17.
  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. Special issue on EuroCG 2018. URL: https://doi.org/10.1016/j.comgeo.2019.07.006.
  11. C. C. Cheng, Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov. Drawing planar graphs with circular arcs. Discrete Comput. Geom., 25:405-418, 2001. URL: https://doi.org/10.1007/s004540010080.
  12. Walter Didimo, Peter Eades, and Giuseppe Liotta. Drawing graphs with right angle crossings. Theoret. Comput. Sci., 412(39):5156-5166, 2011. URL: https://doi.org/10.1016/j.tcs.2011.05.025.
  13. 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.
  14. Vida Dujmović, Joachim Gudmundsson, Pat Morin, and Thomas Wolle. Notes on large angle crossing graphs. In A. Potanin and A. Viglas, editors, Proc. Comput. Australasian Theory Symp. (CATS'10), volume 109 of CRPIT, pages 19-24. Australian Computer Society, 2010. URL: http://dl.acm.org/citation.cfm?id=1862317.1862320.
  15. Peter Eades and Giuseppe Liotta. Right angle crossing graphs and 1-planarity. Discrete Appl. Math., 161(7):961-969, 2013. URL: https://doi.org/10.1016/j.dam.2012.11.019.
  16. Weidong Huang. Using eye tracking to investigate graph layout effects. In Seok-Hee Hong and Kwan-Liu Ma, editors, Proc. Asia-Pacific Symp. Visual. (APVIS'07), pages 97-100. IEEE, 2007. URL: https://doi.org/10.1109/APVIS.2007.329282.
  17. 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.
  18. Weidong Huang, Seok-Hee Hong, and Peter Eades. Effects of crossing angles. In Proc. IEEE VGTC Pacific Visualization (PacificVis'08), pages 41-46, 2008. URL: https://doi.org/10.1109/PACIFICVIS.2008.4475457.
  19. Michael Jünger and Petra Mutzel, editors. Graph Drawing Software. Springer, Berlin, Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-642-18638-7.
  20. Michael Kaufmann and Dorothea Wagner, editors. Drawing Graphs: Methods and Models. Springer, Berlin, Heidelberg, 2001. URL: https://doi.org/10.1007/3-540-44969-8.
  21. Myroslav Kryven, Alexander Ravsky, and Alexander Wolff. Drawing graphs on few circles and few spheres. J. Graph Algorithms Appl., 23(2):371-391, 2019. URL: https://doi.org/10.7155/jgaa.00495.
  22. Mark Lombardi and Robert Hobbs, editors. Mark Lombardi: Global Networks. Independent Curators, 2003. Google Scholar
  23. C. Stanley Ogilvy. Excursions in Geometry. Oxford Univ. Press, New York, 1969. Google Scholar
  24. János Pach, Radoš Radoičić, and Géza Tóth. Relaxing planarity for topological graphs. In Ervin Győri, Gyula O. H. Katona, László Lovász, and Tamás Fleiner, editors, More Sets, Graphs and Numbers: A Salute to Vera Sós and András Hajnal, pages 285-300. Springer Berlin Heidelberg, 2006. URL: https://doi.org/10.1007/978-3-540-32439-3_12.
  25. Helen C. Purchase, John Hamer, Martin Nöllenburg, and Stephen G. Kobourov. On the usability of Lombardi graph drawings. In Walter Didimo and Maurizio Patrignani, editors, Proc. Graph Drawing (GD'12), volume 7704 of LNCS, pages 451-462. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-36763-2_40.
  26. André Schulz. Drawing graphs with few arcs. J. Graph Algorithms Appl., 19(1):393-412, 2015. URL: https://doi.org/10.7155/jgaa.00366.
  27. Kai Xu, Chris Rooney, Peter Passmore, and Dong-Han Ham. A user study on curved edges in graph visualisation. In Philip Cox, Beryl Plimmer, and Peter Rodgers, editors, Proc. Theory Appl. Diagrams (DIAGRAMS'10), volume 7352 of LNCS, pages 306-308. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31223-6_34.
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