3 papers
cs.DS2026
Layer-Respecting Linear Graph Layouts
Alvin Chiu, David Eppstein, Michael T. Goodrich +1
We show how to visualize a graph, , as a layered drawing, layer-respecting arc diagram, or layer-respecting linear cylindric drawing with a minimum number of edge crossing…
cs.DS2025
Exact Learning of Weighted Graphs Using Composite Queries
Michael T. Goodrich, Songyu Liu, Ioannis Panageas
In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, , of a weighted graph, , but we are not given . The prob…
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…