Informatické kolokvium 10.3. Planar graphs have bounded queue-number
Informatické kolokvium 10.3. 2019, 14:00 posluchárna D2
Piotr Micek Ph.D., Department of Theoretical Computer Science, Jagellonská
univerzita, Krakov, Polsko
Planar graphs have bounded queue-number
Abstrakt: 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.