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.