Document Open Access Logo

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Authors Oswin Aichholzer , Alfredo García , Javier Tejel , Birgit Vogtenhuber , Alexandra Weinberger

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.5.pdf
  • Filesize: 1.76 MB
  • 18 pages

Document Identifiers

Author Details

Oswin Aichholzer
  • Institute of Software Technology, Technische Universität Graz, Austria
Alfredo García
  • Departamento de Métodos Estadísticos and IUMA, University of Zaragoza, Spain
Javier Tejel
  • Departamento de Métodos Estadísticos and IUMA, University of Zaragoza, Spain
Birgit Vogtenhuber
  • Institute of Software Technology, Technische Universität Graz, Austria
Alexandra Weinberger
  • Institute of Software Technology, Technische Universität Graz, Austria

Funding

  • Aichholzer, Oswin: Partially supported by the Austrian Science Fund (FWF): W1230 and by H2020-MSCA-RISE project 734922 - CONNECT.
  • García, Alfredo: Supported by H2020-MSCA-RISE project 734922 - CONNECT and Gobierno de Aragón project E41-17R.
  • Tejel, Javier: Supported by H2020-MSCA-RISE project 734922 - CONNECT, Gobierno de Aragón project E41-17R and project PID2019-104129GB-I00 / AEI / 10.13039/501100011033 of the Spanish Ministry of Science and Innovation.
  • Vogtenhuber, Birgit: Partially supported by Austrian Science Fund within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35 and by H2020-MSCA-RISE project 734922 - CONNECT.
  • Weinberger, Alexandra: Supported by the Austrian Science Fund (FWF): W1230 and by H2020-MSCA-RISE project 734922 - CONNECT.

Cite AsGet BibTex

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.5

Abstract

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Graph theory
Keywords
  • Simple drawings
  • simple topological graphs
  • disjoint edges
  • plane matching
  • plane path

Metrics

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

Related Versions

  • Some results of this work have been presented at the Computational Geometry: Young Researchers Forum in 2021 [Oswin Aichholzer et al., 2021] and at the Encuentros de Geometría Computacional 2021 [Oswin Aichholzer et al., 2021].
  • Extended Version https://arxiv.org/abs/2203.06143v1

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 Proc. 31^st European Workshop on Computational Geometry EuroCG '15, pages 57-60, Ljubljana, Slovenia, 2015. URL: http://www.ist.tu-graz.ac.at/files/publications/geometry/aafhpprsv-agdsc-15.pdf.
  2. Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos, and Gelasio Salazar. Shellable drawings and the cylindrical crossing number of K_n. Discrete & Computational Geometry, 52(4):743-753, 2014. URL: https://doi.org/10.1007/s00454-014-9635-0.
  3. Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Plane matchings in simple drawings of complete graphs. In Abstracts of the Computational Geometry: Young Researchers Forum, pages 6-10, 2021. URL: https://cse.buffalo.edu/socg21/files/YRF-Booklet.pdf#page=6.
  4. Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Plane paths in simple drawings of complete graphs. In Abstracts of XIX Encuentros de Geometría Computacional, page 4, 2021. URL: https://quantum-explore.com/wp-content/uploads/2021/06/Actas_egc21.pdf#page=11.
  5. Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Gelasio Salazar, and Birgit Vogtenhuber. Deciding monotonicity of good drawings of the complete graph. In Abstracts XVI Spanish Meeting on Computational Geometry (XVI EGC), pages 33-36, 2015. Google Scholar
  6. Alan Arroyo, Dan McQuillan, R. Bruce Ritcher, and Gelasio Salazar. Drawings of K_n with the same rotation scheme are the same up to Reidemeister moves (Gioan’s theorem). Australasian Journal of Combinatorics, 67:131-144, 2017. Google Scholar
  7. Martin Balko, Radoslav Fulek, and Jan Kynčl. Crossing numbers and combinatorial characterization of monotone drawings of K_n. Discrete Comput. Geom., 53(1):107-143, 2015. URL: https://doi.org/10.1007/s00454-014-9644-z.
  8. Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1):161-166, 1950. URL: https://doi.org/10.2307/1969503.
  9. Jacob Fox and Benny Sudakov. Density theorems for bipartite graphs and related ramsey-type results. Combinatorica, 29(2):153-196, 2009. URL: https://doi.org/10.1007/s00493-009-2475-5.
  10. Radoslav Fulek. Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings. SIAM Journal on Discrete Mathematics, 28(1):116-121, 2014. URL: https://doi.org/10.1137/130925554.
  11. Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Hanani-Tutte, monotone drawings, and level-planarity. In Thirty essays on geometric graph theory, pages 263-287. Springer, New York, NY, 2013. URL: https://doi.org/10.1007/978-1-4614-0110-0_14.
  12. Radoslav Fulek and Andres J. Ruiz-Vargas. Topological graphs: empty triangles and disjoint matchings. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG'13), pages 259-266, 2013. URL: https://doi.org/10.1145/2462356.2462394.
  13. Alfredo García, Alexander Pilz, and Javier Tejel. On plane subgraphs of complete topological drawings. ARS MATHEMATICA CONTEMPORANEA, 20:69-87, 2021. URL: https://doi.org/10.26493/1855-3974.2226.e93.
  14. Emeric Gioan. Complete graph drawings up to triangle mutations. In Graph-Theoretic Concepts in Computer Science. WG 2005. Lecture Notes in Computer Science, vol 3787, pages 139-150. Springer, 2005. URL: https://doi.org/10.1007/11604686_13.
  15. János Pach, József Solymosi, and Gézak Tóth. Unavoidable configurations in complete topological graphs. Discrete Comput Geometry, 30:311-320, 2003. URL: https://doi.org/10.1007/s00454-003-0012-9.
  16. János Pach and Géza Tóth. Disjoint edges in topological graphs. In Proceedings of the 2003 Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT'03), volume 3330, pages 133-140, 2005. URL: https://doi.org/10.1007/978-3-540-30540-8_15.
  17. János Pach and Géza Tóth. Monotone crossing number. In Graph Drawing, pages 278-289. Springer Berlin Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-25878-7_27.
  18. Nabil H. Rafla. The good drawings D_n of the complete graph K_n. PhD thesis, McGill University, Montreal, 1988. URL: https://escholarship.mcgill.ca/concern/file_sets/cv43nx65m?locale=en.
  19. Andres J. Ruiz-Vargas. Empty triangles in complete topological graphs. In Discrete Computational Geometry, volume 53, pages 703-712, 2015. URL: https://doi.org/10.1007/s00454-015-9671-4.
  20. Andres J. Ruiz-Vargas. Many disjoint edges in topological graphs. Computational Geometry, 62:1-13, 2017. URL: https://doi.org/10.1016/j.comgeo.2016.11.003.
  21. Andrew Suk. Disjoint edges in complete topological graphs. Discrete & Computational Geometry, 49(2):280-286, 2013. URL: https://doi.org/10.1007/s00454-012-9481-x.
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