In this thesis we present an approach to auto-generate highly structured meshes for applications where the domain changes over time. Especially in the area of PDE-constrained shape optimization, a key bottle neck in the computation is the generation of stable meshes in each iteration. The proposed approach possesses the advantages of structured meshes and is still capable of resolving boundaries accurately. Through the specific structure of the meshes, computational cost is reduced not only while generating the mesh but in the assembly of the governing linear system of equations as well. Additionally, we present an approach to apply Krylov subspace recycling to evolving domains, a state of the art method to solve large sparse linear systems of equations. We present results in two and three dimensions and how the meshes evolve in a gradient-based shape optimization setting.