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.
(Blog post: Stretch, average stretch, and expected stretch of spanning trees)
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 28 (2): 31:1–31:18, 2026, doi:10.46298/dmtcs.16770.
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})\).