An Improved Upper Bound on the Queue Number of Planar Graphs

被引:1
作者
Bekos, Michael [1 ]
Gronemann, Martin [2 ]
Raftopoulou, Chrysanthi N. [3 ]
机构
[1] Univ Ioannina, Dept Math, Univ Campus, GR-45110 Ioannina, Greece
[2] TU Wien, Algorithms & Complex Grp, Favoritenstr 9-11, A-1040 Vienna, Austria
[3] Natl Tech Univ Athens, Sch Appl Math & Phys Sci, Iroon Polytexneiou 9, Athens 15780, Greece
关键词
Linear layouts; Queue number; Planar graphs; TRACK LAYOUTS; BANDWIDTH;
D O I
10.1007/s00453-022-01037-4
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
A k-queue layout is a special type of a linear layout, in which the linear order avoids (k +1)-rainbows, that is, k +1 independent edges that pairwise form a nested pair. The optimization goal is to determine the queue number of a graph, which is defined as the minimum value of k for which a k-queue layout is feasible. Recently, Dujmovie et al. [J. ACM, 67(4), 22:1-38, 2020] showed that the queue number of planar graphs is at most 49, thus settling in the positive a long-standing conjecture by Heath, Leighton and Rosenberg. To achieve this breakthrough result, their approach involves three different techniques: (1) an algorithm to obtain 2-queue layouts of outerplanar graphs, (2) an algorithm to obtain 5-queue layouts of planar 3-trees, and (3) a decomposition of a planar graph into so-called tripods. In this work, we push further each of these techniques to obtain the first non-trivial improvement of the upper bound on the queue number of planar graphs from 49 to 42.
引用
收藏
页码:544 / 562
页数:19
相关论文
共 23 条
[1]   Queue Layouts of Planar 3-Trees [J].
Alam, Jawaherul Md. ;
Bekos, Michael A. ;
Gronemann, Martin ;
Kaufmann, Michael ;
Pupyrev, Sergey .
ALGORITHMICA, 2020, 82 (09) :2564-2585
[2]   Track Layouts, Layered Path Decompositions, and Leveled Planarity [J].
Bannister, Michael J. ;
Devanny, William E. ;
Dujmovic, Vida ;
Eppstein, David ;
Wood, David R. .
ALGORITHMICA, 2019, 81 (04) :1561-1583
[3]   On bandwidth, cutwidth, and quotient graphs [J].
Barth, D ;
Pellegrini, F ;
Raspaud, A ;
Roman, J .
RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1995, 29 (06) :487-508
[4]  
Bekos MA, 2020, J COMPUT GEOM, V11, P332
[5]   PLANAR GRAPHS OF BOUNDED DEGREE HAVE BOUNDED QUEUE NUMBER [J].
Bekos, Michael A. ;
Foerster, Henry ;
Gronemann, Martin ;
Mchedlidze, Tamara ;
Montecchiani, Fabrizio ;
Raftopoulou, Chrysanthi ;
Ueckerdt, Torsten .
SIAM JOURNAL ON COMPUTING, 2019, 48 (05) :1487-1502
[6]   BOOK THICKNESS OF A GRAPH [J].
BERNHART, F ;
KAINEN, PC .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) :320-331
[7]   THE BANDWIDTH PROBLEM FOR GRAPHS AND MATRICES - A SURVEY [J].
CHINN, PZ ;
CHVATALOVA, J ;
DEWDNEY, AK ;
GIBBS, NE .
JOURNAL OF GRAPH THEORY, 1982, 6 (03) :223-254
[8]   ON THE QUEUE NUMBER OF PLANAR GRAPHS [J].
Di Battista, Giuseppe ;
Frati, Fabrizio ;
Pach, Janos .
SIAM JOURNAL ON COMPUTING, 2013, 42 (06) :2243-2285
[9]   A survey of graph layout problems [J].
Díaz, J ;
Petit, J ;
Serna, M .
ACM COMPUTING SURVEYS, 2002, 34 (03) :313-356
[10]  
Dujmovic V, 2004, DISCRETE MATH THEOR, V6, P497