Publications with Songyu (Alfred) Liu
- Bandwidth vs BFS width in matrix reordering, graph
reconstruction, and graph drawing.
D. Eppstein, M. T. Goodrich, and S. Liu.
arXiv:2505.10789.
Proc. 33rd Annual European Symposium on Algorithms (ESA 2025).
Leibniz International Proceedings in Informatics (LIPIcs) 351, 2025, pp. 69:1–69:17.
In graphs of bounded bandwidth, the number of vertices per level of a breadth-first search tree is at most polylogarithmic, with the exponent of the polylogarithm both upper and lower bounded by functions of the bandwidth. This has applications to the Cuthull-McKee heuristic and reverse Cuthull-McKee heuristic in sparse numerical algebra, to reconstructing an unknown graph by shortest distance queries, and to drawing graphs as arc diagrams of small height.