  While the theory of labeled well-quasi-order has received significant
attention in the graph setting, it has not yet been considered in the context
of permutation patterns. We initiate this study here, and using labeled
well-quasi-order are able to subsume and extend all of the well-quasi-order
results in the permutation patterns literature. Connections to the graph
setting are emphasized throughout. In particular, we establish that a
permutation class is labeled well-quasi-ordered if and only if its
corresponding graph class is also labeled well-quasi-ordered.
