Showing 2025Show all
3 papers · 1 filter
cs.CG2025
Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan +1
We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a meas…
cs.CG2025
Visualizing Treewidth
Alvin Chiu, Thomas Depian, David Eppstein +2
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly sho…
cs.DS2025
Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
David Eppstein, Michael T. Goodrich, Songyu Liu
We provide the first approximation quality guarantees for the Cuthull-McKee heuristic for reordering symmetric matrices to have low bandwidth, and we provide an algorithm for recon…