EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Crossing Number of Simple 3-Plane Drawings

Torsten Ueckerdt, Miriam Goetze, Michael Hoffmann, Ignaz Rutter

Journal of Graph Algorithms and Applications · 28.04.2026 · 30 (2) · 1-21

DOI: 10.7155/jgaa.v30i2.3117 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 28.04.2026. Verfasst von Torsten Ueckerdt und 3 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs [9] can be used to count the crossings in terms of the number n of vertices. As a main result, we show that every 3-plane drawing has at most 5.5(n − 2) crossings, which is tight. In particular, it follows that every 3-planar graph on n vertices has crossing number at most 5.5n, which improves upon a recent bound [3] of 6.6n. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most 5.5(n − 2) edges.

Zitieren

APA

Ueckerdt, T., Goetze, M., Hoffmann, M., & Rutter, I. (2026). Crossing Number of Simple 3-Plane Drawings. Journal of Graph Algorithms and Applications, 30(2), 1-21. https://doi.org/10.7155/jgaa.v30i2.3117

Vancouver

Ueckerdt T, Goetze M, Hoffmann M, Rutter I. Crossing Number of Simple 3-Plane Drawings. Journal of Graph Algorithms and Applications. 2026;30(2):1-21. doi:10.7155/jgaa.v30i2.3117

BibTeX
@article{Ueckerdt2026,
  author = {Ueckerdt, Torsten and Goetze, Miriam and Hoffmann, Michael and Rutter, Ignaz},
  title = {Crossing Number of Simple 3-Plane Drawings},
  journal = {Journal of Graph Algorithms and Applications},
  year = {2026},
  volume = {30},
  number = {2},
  pages = {1--21},
  doi = {10.7155/jgaa.v30i2.3117}
}
Kostenlos starten →