Publications with William Maxwell
Low-stretch spanning trees of graphs with bounded width.
G. Borradaile,
E. Chambers,
D. Eppstein,
W. Maxwell, and
A. Nayyeri.
arXiv:2004.08375.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm
Theory (SWAT 2020).
Leibniz International
Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19, doi:10.4230/LIPIcs.SWAT.2020.15.
We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.
On the treewidth of Hanoi graphs.
D. Eppstein,
D. Frishberg, and
W. Maxwell.
arXiv:2005.00179.
Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
Leibniz International
Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21, doi:10.4230/LIPIcs.FUN.2021.13.
Theor. Comput. Sci. 906: 1–17, 2022, doi:10.1016/j.tcs.2021.12.014.
The \(n\)-disc \(p\)-peg Hanoi graphs have treewidth within a polynomial factor of \(n^{p-1}\). In a follow-up paper, "On the expansion of Hanoi graphs", we eliminated the polynomial factor.
On the expansion of Hanoi graphs.
D. Eppstein,
D. Frishberg, and
W. Maxwell.
arXiv:2510.18010
Discrete Mathematics & Theoretical Computer Science, to
appear.
In a previous paper, "On the treewidth of Hanoi graphs", we showed that \(n\)-disc \(p\)-peg Hanoi graphs have treewidth within a polynomial factor of \(n^{p-1}\). Here we consider expansion instead, and prove that both it and the treewidth are \(\Theta(n^{p-1})\).