6 papers · 1 filter
Hamiltonian Cycles in Subdivided Doubles
David Eppstein
The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric (edge-transitive but not vertex-transitive) graphs, and can be used…
Better Late than Never: the Complexity of Arrangements of Polyhedra
Boris Aronov, Sang Won Bae, Sergio Cabello +4
Let be the subdivision of induced by convex polyhedra having facets in total. We prove that has combinatorial complexity $O(m^{\l…
String Graph Obstacles of High Girth and of Bounded Degree
Maria Chudnovsky, David Eppstein, David Fischer
A string graph is the intersection graph of curves in the plane. KratochvÃl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for…
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…
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…
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…