Queue number above 2 for planar graphs?

87 Views Asked by At

Are there any known planar graphs with queue number greater than $2$?


The queue number of a graph counts the minimum number of subsets that the edges must be divided into to avoid all nested pairs of edges, minimising over all orderings of the vertices. In other words, if $a < b < c <d$ are four distinct vertices in the ordering, and both $ad$ and $bc$ are edges in the graph, then they must be in different subsets.

In $2019$, Dujmović et al. proved that all planar graphs have queue number at most $49$. In $2021$, Bekos et al. improved the upper bound to $42$.

In contrast, the largest queue number of any planar graph I know of is $2$. For instance, the $3$-sun graph, with $6$ vertices and $9$ edges, has queue number $2$. A $2013$ paper by Battista et al. claimed that "no lower bound greater than two seems to be known for the queue number of planar graphs."

Is the highest known queue number of any planar graph $2$? Is it plausible that all planar graphs have queue number at most $2$?