A concrete tripod-decomposition counterexample shows that Claim 2 in the 42-queue layout paper of Bekos, Gronemann, and Raftopoulou is false, so the 42 bound is not proved.
A note on planar partial 3-trees
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
It implicitly follows from the work of [Colbourn, El-Mallah: On two dual classes of planar graphs. Discrete Mathematics 80(1): 21-40 (1990)] that every planar partial 3-tree is a subgraph of a planar 3-tree. This fact has already enabled to prove a couple of results for planar partial 3-trees by induction on the structure of the underlying planar 3-tree completion. We provide an explicit proof of this observation and strengthen it by showing that one can keep the plane drawing of the input graph unchanged.
citation-role summary
background 1
citation-polarity summary
fields
cs.DM 1years
2026 1verdicts
ACCEPT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
A Gap in the 42-Queue Layout Algorithm for Planar Graphs
A concrete tripod-decomposition counterexample shows that Claim 2 in the 42-queue layout paper of Bekos, Gronemann, and Raftopoulou is false, so the 42 bound is not proved.