Stack number and queue number of graphs

Abstract: In this paper we give an overview of the graph invariants queue number and stack number (the latter also called the page number or book thickness). Due to their similarity, it has been studied for a long time, whether one of them is bounded in terms of the other. It is now known that the stack number is not bounded by the queue number. We present a simplified proof of this result. We also survey the known results about possible stack number bound on the queue number. This preprint is a rework of the bachelor thesis [29].

This page was built for publication: Stack number and queue number of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436857)