Showing reachability between source trees

2010-05-26T18:10:00.000-07:00

From A log-space algorithm for reachability in planar acyclic digraphs with few sources, joint work with Chris Bourke and N. V. Vinodchandran.

This figure helps visualize two cases for reachability after an update of the explored region. The key insight of the paper was to reduce the locality of the search to these "back and forth" between trees.

Changing Automorphisms

2010-05-26T17:46:00.000-07:00

From Automorphism groups of a graph and a vertex deleted subgraph, joint work with Stephen G. Hartke, Hannah Kolb, and Jared Nishikawa.

These figures demonstrate the behavior of the final construction: a graph G with automorphism group isomorphic to a group Γ₁ with a vertex v so that after deleting v, the automorphism group is isomorphic to a group Γ₂. What is most interesting in this result is that there does not need to be any relationship between the two groups.

Proof by Picture

Showing reachability between source trees

Changing Automorphisms