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…