Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1007/s00453-020-00697-4 | ALGORITHMICA |
Keywords | DocType | Volume |
Queue layouts,Constant queue number,Planar 3-trees | Journal | 82.0 |
Issue | ISSN | Citations |
9 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Md. Jawaherul Alam | 1 | 78 | 14.24 |
| Michael A. Bekos | 2 | 250 | 38.21 |
| Martin Gronemann | 3 | 26 | 7.96 |
| Michael Kaufmann | 4 | 1224 | 107.33 |
| Sergey Pupyrev | 5 | 148 | 17.77 |