Bekos, Michael A., Foerster, Henry, Gronemann, Martin ORCID: 0000-0003-2565-090X, Mchedlidze, Tamara, Montecchiani, Fabrizio ORCID: 0000-0002-0543-8912, Raftopoulou, Chrysanthi and Ueckerdt, Torsten (2019). PLANAR GRAPHS OF BOUNDED DEGREE HAVE BOUNDED QUEUE NUMBER. SIAM J. Comput., 48 (5). S. 1487 - 1503. PHILADELPHIA: SIAM PUBLICATIONS. ISSN 1095-7111

Full text not available from this repository.

Abstract

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg [SIAM T. Discrete Math., 5 (1992), pp. 398-412] states that the queue number of planar graphs is bounded. This conjecture has been partially settled in the positive for several subfamilies of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree has bounded queue number.

Item Type: Journal Article
Creators:
CreatorsEmailORCIDORCID Put Code
Bekos, Michael A.UNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Foerster, HenryUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Gronemann, MartinUNSPECIFIEDorcid.org/0000-0003-2565-090XUNSPECIFIED
Mchedlidze, TamaraUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Montecchiani, FabrizioUNSPECIFIEDorcid.org/0000-0002-0543-8912UNSPECIFIED
Raftopoulou, ChrysanthiUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Ueckerdt, TorstenUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
URN: urn:nbn:de:hbz:38-160396
DOI: 10.1137/19M125340X
Journal or Publication Title: SIAM J. Comput.
Volume: 48
Number: 5
Page Range: S. 1487 - 1503
Date: 2019
Publisher: SIAM PUBLICATIONS
Place of Publication: PHILADELPHIA
ISSN: 1095-7111
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Uncontrolled Keywords:
KeywordsLanguage
TRACK LAYOUTS; STACKSMultiple languages
Computer Science, Theory & Methods; Mathematics, AppliedMultiple languages
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/16039

Downloads

Downloads per month over past year

Altmetric

Export

Actions (login required)

View Item View Item