News and events archive

Informatics Colloquium 10.3. 2019, 14:00 lecture hall D2 Piotr Micek Ph.D., Department of Theoretical Computer Science, Jagiellonian University, Cracow, Poland Planar graphs have bounded queue-number Abstract: Stacks and queues are fundamental data structures in computer science. But what is more powerful, a stack or a queue? In 1992, Heath, Leighton, and Rosenberg developed a graph-theoretic formulation of this question, where they defined the graph parameters stack-number and queue-number which respectively measure the power of stacks and queues to represent a given graph. It is still open whether every graph has stack-number bounded by a function of its queue-number, or whether every graph has queue-number bounded by a function of its stack-number. Planar graphs were the simplest class of graphs where it was unknown whether the queue-number is bounded. (The stack number of planar graphs is at most 4.) We show that planar graphs have queue-number at most 48. The key to the proof is a new structural tool called layered partitions, and the result that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. We call the latter result the product structure theorem for planar graphs. We will discuss further applications, including adjacency labelings, nonrepetitive colorings, and p-centered colorings.