To appear with unknown date
Visualizing treewidth.
A. Chiu,
T. Depian,
D. Eppstein,
M. T. Goodrich,
and
M. Nöllenburg.
arXiv:2508.19935.
33rd International Symposium on Graph Drawing and Network
Visualization.
Leibniz
International Proceedings in Informatics (LIPIcs) 357, 2025,
pp. 17:1–17:20, doi:10.4230/LIPIcs.GD.2025.17.
J. Graph Algorithms & Applications, to appear.
We experiment with metro-map style visualizations of tree decompositions of graphs. Here, the bags of a tree decomposition are visualized as stations on a metro system, and the vertices of a graph are visualized as metro lines passing through certain stations. Within each bag we display a drawing of the induced subgraph of the bag.
Hamiltonian cycles in subdivided doubles.
D. Eppstein.
arXiv:2510.18359.
Ars Mathematica Contemporanea, to appear.
The subdivided double construction turns a 4-regular graph into a bigger 4-regular graph, by subdividing each edge and doubling each vertex. We prove that the resulting graphs, which include the Folkman graph, have the following curious property: every Hamiltonian cycle (of which there are exponentially many) is complementary to another Hamiltonian cycle.
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})\).