Universität zu Köln

Alam, Jawaherul Md., Bekos, Michael A., Gronemann, Martin ORCID: 0000-0003-2565-090X, Kaufmann, Michael and Pupyrev, Sergey (2020). Queue Layouts of Planar 3-Trees. Algorithmica, 82 (9). S. 2564 - 2586. NEW YORK: SPRINGER. ISSN 1432-0541

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Alam, Jawaherul Md. UNSPECIFIED UNSPECIFIED UNSPECIFIED Bekos, Michael A. UNSPECIFIED UNSPECIFIED UNSPECIFIED Gronemann, Martin UNSPECIFIED orcid.org/0000-0003-2565-090X UNSPECIFIED Kaufmann, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Pupyrev, Sergey UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-340424
DOI:	10.1007/s00453-020-00697-4
Journal or Publication Title:	Algorithmica
Volume:	82
Number:	9
Page Range:	S. 2564 - 2586
Date:	2020
Publisher:	SPRINGER
Place of Publication:	NEW YORK
ISSN:	1432-0541
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:	no entry
Uncontrolled Keywords:	Keywords Language GRAPHS; STACKS; NUMBER Multiple languages Computer Science, Software Engineering; Mathematics, Applied Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/34042