David Hume *cancelled*

A coarse geometric approach to graph layout problems

Graph layout problems seek representations of finite graphs which minimise some specified cost function. Examples include cutwidth, treewidth and bandwidth. They have many applications, for example in circuit design (very large scale integration), bioinformatics and code creation. Typically, finding optimal representations is NP-hard, even for restricted classes of graphs (such as planar graphs). In this talk, we present a coarse geometric approach to graph layout problems - creating a range of new functions which behave monotonically with respect to coarse embeddings between bounded degree graphs, and as such have potential applications in geometric group theory. Using this coarse approach, we are able to calculate the asymptotic growth of several of these cost functions for subgraphs of Cayley graphs of various classes of finitely generated groups, including all polycylic groups.

This is joint work with Wanying Huang, Samuel Kelly and Ryan Lam.