We develop an auto-encoder-type nonlinear dimensionality reduction algorithm to enable the construction of reduced order models of systems governed by convection-dominated nonlinear partial differential equations (PDEs), i.e. snapshots of solutions with large Kolmogorov n-width. Although several existing nonlinear manifold learning methods, such as LLE, ISOMAP, MDS, etc., appear as compelling candidates to reduce the dimensionality of such data, most are not applicable to reduced order modeling of PDEs, because: (i) they typically lack a straightforward mapping from the latent space to the high-dimensional physical space, and (ii) the identified latent variables are often difficult to interpret. In our proposed method, these limitations are overcome by training a low-rank diffeomorphic spatio-temporal grid that registers the output sequence of the PDEs on a non-uniform parameter/time-varying grid, such that the Kolmogorov n-width of the mapped data on the learned grid is minimized. We demonstrate the efficacy and interpretability of our proposed approach on several challenging manufactured computer vision-inspired tasks and physical systems.