Graph Layouts via Layered Separators

Vida Dujmović

In this talk I will show how a fairly unknown type of graph separators can be used to show that every n-vertex planar graph has track number and queue number at most O(log n). Time permitting, I will show how the same tool can also give O(log n) non-repetitive chromatic number for planar graphs. All the results are the improvements over the previous best known bounds.