2020/08/19 by Sujoy Bhore, Robert Ganian, Bhore, Sujoy +5 · 3 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2008.08288
openalex publication_date 2020/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An h-queue layout of a graph G consists of a linear order of its vertices and a partition of its edges into h queues, such that no two independent edges of the same queue nest. The minimum h such that G admits an h-queue layout is the queue number of G. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph G has queue number 1 and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of G. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary h.