Queue Layouts of Planar 3-Trees
- PDF / 3,387,975 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 211 Views
Queue Layouts of Planar 3‑Trees Jawaherul Md. Alam1 · Michael A. Bekos2 · Martin Gronemann3 · Michael Kaufmann2 · Sergey Pupyrev1 Received: 6 October 2018 / Accepted: 6 March 2020 © The Author(s) 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. Keywords Queue layouts · Constant queue number · Planar 3-trees
A preliminary version of this article has appeared in the proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018). This work is supported by the DFG Grant Ka812/17-1 and DAAD Project 57419183. * Michael A. Bekos [email protected]‑tuebingen.de Jawaherul Md. Alam [email protected] Martin Gronemann [email protected]‑koeln.de Michael Kaufmann [email protected]‑tuebingen.de Sergey Pupyrev [email protected] 1
Department of Computer Science, University of Arizona, Tucson, USA
2
Institut für Informatik, Universität Tübingen, Tübingen, Germany
3
Institut für Informatik, Universität zu Köln, Köln, Germany
13
Vol.:(0123456789)
Algorithmica
1 Introduction In a queue layout [19], the vertices of a graph are restricted to a line and its edges are drawn at different half-planes delimited by this line, called queues. The task is to find a linear order of the vertices along the underlying line and a corresponding assignment of the edges of the graph to the queues, so that no two independent edges of the same queue are nested; see Fig. 1 for an illustration. Recall that two edges are called independent, if they do not share an endvertex. The queue number of a graph is the smallest number of queues that are required by any queue layout of the graph. Note that queue layouts form the “dual” concept of stack layouts [22] (widely known also as book embeddings), which do not allow two edges of the same stack to cross. Apart from the intriguing theoretical interest, queue layouts find applications in several domains [3, 18, 23, 29]. As a result, they have been studied extensively over the years [5, 8, 13, 17, 19, 24, 25, 27–30]. The most remarkable result in this area is due to Dujmović et al. [9], who recently proved that planar graphs have constant queue number (by the time of writing at most 49) improving upon a series of results [2, 5, 7] and thus settling in the positive an old conjecture by Heath, Leighton and Rosenberg [18]. Notably, this breakthrough result has several
Data Loading...
