Congratulations, Dr. Chiu!
Yesterday, Alvin Chiu passed his Ph.D. defense. Alvin has been a student of Mike Goodrich at UC Irvine, is one of my coauthors, and is currently my teaching assistant for my computational geometry course.
He came to UCI from Georgia Tech, where he already had an undergraduate research paper on counting the number of ways an origami pattern can be folded, with William Hoganson, Tom Hull, and Sylvia Wu: “Counting locally flat-foldable origami configurations via 3-coloring graphs” [arXiv:1910.01278; Graphs and Combinatorics 2020, doi:10.1007/s00373-020-02240-2].
Alvin’s dissertation, Witness Drawings in Structure and Geography for Graph Visualization, is on graph drawing, with a more practical focus than my own usual theoretical approach. It takes as its motivating theme the idea that graph drawings should not merely faithfully represent a given graph (different graphs should have different drawings) and allow users to find the information they need in it, but they should also represent important graph properties or data, such as planarity, in a way that allows both for efficient checks of these properties and for readers to be able to clearly see that the property is valid. For example, drawings of planar graphs should be non-crossing (demonstrating that the graph is planar) but more than this, they should be sufficiently uncluttered that readers can clearly tell that they are planar.
I’ve already written here about two of the three publications that went into Alvin’s dissertation: “Manipulating weights to improve stress-graph drawings of 3-connected planar graphs” (from Graph Drawing 2023) and “Visualizing treewidth” (from Graph Drawing 2025). So rather than repeating that material, I thought it would make sense here to say more about the third of these publications, “Circle quasi-cartograms: Dorling cartograms with edge connections and relaxed overlap conditions” [with Tarlan Bahadori, Ahmed Eldawy, and Mike Goodrich, GeoHCC 2025, doi:10.1145/3764917.377133].
The basic idea here is that of a cartogram, a distorted map of a geographic region where the areas of each subregion represent some kind of statistical datum about the subregion rather than its physical shape and size. A Dorling cartogram represents each subregion as a circular disk of the appropriate area, not overlapping any of the other disks. There is a free parameter, the scale of these disks; if they are all scaled to be very small, they can be placed at their correct geographic positions, but this small scale causes the information in the cartogram to be difficult to discern. On the other hand, if the scale is increased, the disks cannot all fit in their correct geographic locations; the cartogram necessarily distorts both geographic position, and, more subtly, the topological connections between the disks. For instance, if we draw a graph of the adjacencies between bordering subregions, then it will for the most part be planar for a geographic placement of vertices at the center of each region, but the distortions caused by a larger cartogram scale can lead to nonplanarities.
Alvin’s paper on cartograms tries to ameliorate these problems with Dorling cartograms by relaxing their hard non-overlap constraints. Instead, he uses a force-based graph drawing system in which the vertices move to minimize an energy resulting from the combination of three forces: attractions between the vertices and their correct geographic locations, and between pairs of neighboring vertices, but repulsions between vertices whose circles overlap, depending on the degree of overlap. These are controlled by three parameters that set the scale of the circles and the relative strengths of these three forces. Their results are tested experimentally, showing that even when a cartogram with no overlap is desired as the eventual result, this method can significantly reduce the mixing of vertices from distinct regions, while paying for this by introducing smaller-scale edge crossings.
Congratulations, Alvin!