Another UC Irvine doctoral student, Songyu (Alfred) Liu, successfully passed his doctoral defense this week, co-advised by Mike Goodrich and me.

Alfred came to UCI in 2020, initially working with cognitive scientist Mark Steyvers, who has a joint appointment in computer science. Their work eventually turned into a 2024 publication, “Combining Human and AI Strengths in Object Counting under Information Asymmetry”, in the 12th AAAI Conference on Human Computation and Crowdsourcing (2024), but in the meantime Alfred decided that he preferred topics that were more directly computational, and switched to working with Mike Goodrich (and eventually me).

The three topics of his doctoral dissertation are reconstructing graphs from shortest path queries (the sort of information you might obtain from the Unix ping command), connections between different graph width parameters, and graph drawing, and are represented in an overlapping way by the three publications that Alfred combined to form his thesis:

  • “Exact learning of weighted graphs using composite queries” (with Goodrich and Ioannis Panageas, IWOCA 2025, arXiv:2511.14882), concerns reconstruction using weighted shortest path and distance queries, generalizing previous results on unweighted graphs. The main result is that for a given connected graph with bounded degree and \(n\) vertices, with edge weights drawn from a power-law distribution, the graph can be reconstructed with \(O(n^{3/2})\) queries, matching what was known for unweighted graphs.

  • I’ve written here before about “Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing” (with Goodrich and me, ESA 2025, arXiv:2505.10789), which I think is the strongest of the three papers. It shows that a simple and widely used breadth-first search based approximation to graph bandwidth, the Cuthill–McKee algorithm, provides a polylogarithmic approximation to bounded bandwidth, with an exponent in the polylogarithm that depends on the bandwidth, and that this dependence is necessary. Applications include reconstruction of bounded-bandwidth graphs in a near-linear number of queries, and drawing graphs as arc diagrams using arcs of small height.

    Some later work by others on similar problems is also worth mentioning here. “Cutwidth versus BFS-width with applications to graph reconstruction from distance queries” (Chirag Kaudan and Amir Nayyeri, SWAT 2026), shows that the same BFS-based heuristic approximates a stronger graph width parameter, cutwidth, with an approximation ratio that is sublinear for bounded cutwidth, with an exponent that depends on the cutwidth. And “Forbidden subgraphs of graphs with low bandwidth” (Maria Chudnovsky, Daniel Lokshtanov, and Eran Nevo, STOC 2026, arXiv:2609.01949) provides a significantly more accurate (but likely less practical) approximation to bandwidth, with an approximation ratio that is bounded rather than polylogarithmic for bounded bandwidth.

  • “Layer-respecting linear graph layouts” (by Alvin Chiu, me, Goodrich, and Alfred, CCCG 2026, arXiv:2607.06968) starts with a graph that has already been partitioned into layers, such as would be obtained by using BFS to approximate bandwidth or cutwidth. For several variations on graph drawing styles that draw the vertices in separate layers or in a single linear sequence with each layer contiguous, we use dynamic programming to optimally order the vertices within each layer in order to minimize the number of crossings in the drawing.

Congratulations, Alfred!

(Discuss on Mastodon)