To appear with unknown date
Non-Euclidean Erdős–Anning theorems.
D. Eppstein.
arXiv:2401.06328.
41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan.
Leibniz
International Proceedings in Informatics (LIPIcs) 332, 2025,
pp. 46:1–46:15.
J. Computational Geometry (special issue for SoCG 2025), to appear.
Non-collinear point sets with integer distances must be finite, for strictly convex distance functions on the plane, for two-dimensional complete Riemannian manifolds of bounded genus, and for geodesic distance on convex surfaces in 3d.
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.
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.