2018/08/31 by Jawaherul Md. Alam, Michael A. Bekos, Alam, Jawaherul Md. +7 · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1808.10841
openalex publication_date 2018/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 G is 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. As opposed to general planar graphs, whose queue number is not known to be bounded by a constant, the queue number of planar 3-trees has been shown to be at most seven. In this work, we improve the upper bound to five. We also show that there exist planar 3-trees, whose queue number is at least four; this is the first example of a planar graph with queue number greater than three.