This record is in review state, the data has not yet been validated.
Crossing Number of Simple 3-Plane Drawings
Loading...
Author / Producer
Date
2025
Publication Type
Book Review
ETH Bibliography
yes
Citations
Altmetric
Data
Rights / License
Abstract
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 [Kaufmann et al., 2024] 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 [Bekos et al., 2024] 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
Publisher
Dagstuhl Publishing
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Graph Drawings
Organisational unit
02150 - Dep. Informatik / Dep. of Computer Science