Tim Johnson, one of the students working in the UCI Center for Algorithms and Theory of Computation, passed his dissertation defense today. Tim has been supervised by Mike Goodrich, with a dissertation on graph drawing. He’s also my co-author on three papers: one at ISAAC 2017 on representing the vertices and adjacencies of graphs by touching squares, and two at ALENEX 2018 and ICALP 2018 on dynamic sorting.

Tim has studied low ply drawings, in which each vertex should have a region of influence, a disk of radius proportional to its longest edge, with only a small number of these regions overlapping at any point. But the largest part of his research in graph drawing concerns the visualization of graphs that represent algorithms or code, as part of a project to use these visualizations to find security vulnerabilities. His work in this area also includes compact drawings of the flowcharts of structured programs, and a novel recursive graph traversal method that combines depth-first and breadth-first searching and produces better visualizations than either for control flow graphs. The traversal can be described recursively, much like depth-first search, but with a vertex expansion algorithm that makes two loops over the adjacency list. The first loop finds unincluded vertices and includes them in the search tree as children of the current vertex. Then, the second loop recursively expands each new child. I think this is almost the same (modulo reversal of the adjacency list) as the not-DFS that you get by replacing the queue of BFS by a stack, giving an alternative non-recursive method for its construction.

Tim is heading to nearby Aliso Viejo, where he will be working for Microsoft as a software engineer on a cloud database project. But when I asked him about his plans, he suggested that he may not be done with research, and indeed he already has some new material, too recent to have been included in his dissertation, in the Graph Drawing 2018 poster session.

Congratulations, Tim!