We describe a transition system that generalizes standard transition-based dependency parsing techniques to generate a graph rather than a tree.  Our system includes a cache with fixed size m, and we characterize the relationship between the parameter m and the class of graphs that can be produced through the graph-theoretic concept of tree decomposition.  We train a sequence-to-sequence neural model based on this system to parse text into Abstract Meaning Representation (AMR).