Martha Osegueda, one of Mike Goodrich’s students at UC Irvine, successfully defended her doctoral dissertation yesterday. Martha is originally Salvadorean, and came to UCI from an undergraduate degree at the University of Texas El Paso. Her research at UCI has spanned a wide variety of topics in graph drawing, phylogeny, computational geometry, and parallel query complexity:

  • “Minimum-width drawings of phylogenetic trees” from COCOA 2019 (doi:10.1007/978-3-030-36412-0_4) is about drawing evolutionary trees compactly. For the version of tree drawing they study, it turns out to be NP-hard when the order of the leaves is unconstrained but linear-time solvable for fixed leaf orderings.

  • “Reconstructing binary trees in parallel” from SPAA 2020 (arXiv:2006.15259) involved the reconstruction of evolutionary trees from queries asking which pair of a triple of species is closest.

  • “Concatenation arguments and their applications to polyominoes and polycubes”, in CGTA 2021 (doi:10.1016/j.comgeo.2021.101790) and “On the number of compositions of two polycubes” from EuroComb 2021 (doi:10.1007/978-3-030-83823-2_12) strengthen the known lower bounds on the growth rates of polyominoes and polycubes, using arguments based on counting ways of gluing pairs of smaller polyforms into larger ones.

  • “Angles of arc-polygons and Lombardi drawings of cacti”, from CCCG 2021 (arXiv:2107.03615) is my only collaboration with Martha and one I have posted about here. It characterizes the vertex angles that are possible in triangles with circular-arc sides, and uses that characterization to prove the existence of a Lombardi drawing for any cactus graph.

  • “Parallel network mapping algorithms” from SPAA 2021 (doi:10.1145/3409964.3461822) and “Mapping Networks via parallel \(k\)th-hop traceroute queries” from STACS 2022 (doi:10.4230/LIPIcs.STACS.2022.4) are on traceroute-like problems: mapping the structure of a computer communication network using a small number of parallel rounds of pings to determine distances from nodes on the network.

  • “Taming the knight’s tour: Minimizing turns and crossings” from FUN 2021 and TCS 2022 (doi:10.1016/j.tcs.2021.12.002) shows how to move a chess knight around all of the squares of a chessboard, touching each square once, so that the number of times the knight’s path crosses itself or deviates from a straight path are both simultaneously approximately minimized.

  • “Diamonds are forever in the blockchain: Geometric polyhedral point-set pattern matching” is her newest work, in submission. It studies problems of aligning a polyhedron to sample points from a similarly-shaped surface, motivated by an application in tracing the provenance of ethically sourced diamonds.

Despite all of these good publications, Mike tells me that it was difficult to persuade Martha that she had done enough for a doctorate. But she had, easily, and now she’s moving on to a position at Meta. Congratulations, Martha!

(Discuss on Mastodon)