Universität zu Köln

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:	Creators Email ORCID ORCID Put Code Bekos, Michael A. UNSPECIFIED UNSPECIFIED UNSPECIFIED Foerster, Henry UNSPECIFIED UNSPECIFIED UNSPECIFIED Gronemann, Martin UNSPECIFIED orcid.org/0000-0003-2565-090X UNSPECIFIED Mchedlidze, Tamara UNSPECIFIED UNSPECIFIED UNSPECIFIED Montecchiani, Fabrizio UNSPECIFIED orcid.org/0000-0002-0543-8912 UNSPECIFIED Raftopoulou, Chrysanthi UNSPECIFIED UNSPECIFIED UNSPECIFIED Ueckerdt, Torsten UNSPECIFIED UNSPECIFIED UNSPECIFIED
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:	Keywords Language TRACK LAYOUTS; STACKS Multiple languages Computer Science, Theory & Methods; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/16039