Queue Layouts of Planar 3-Trees
Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Sergey Pupyrev · Algorithmica · 2020
Abstract A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues , so that no two independent edges of the same queue are nested. The queue number of graph G is defined as the minimum number of queues required by any queue layout of G . In this paper, we continue the study of the queue number of planar 3-trees, which form a well-studied subclass of planar graphs. Prior to this work, it was known that the queue number of planar 3-trees is at most seven. In this work, we improve this upper bound to five. We also show that there exist planar 3-trees whose queue number is at least four. Notably, this is the first example of a planar graph with queue number greater than three.