Project Proposal CS598JGE, Fall 2009: Partitioning quadrilateral meshes into structured submeshes

Quadrilateral meshes have many important applications in computer graphics, scientific computing (finite element simulations) and surface modeling. If we view the quadrilateral mesh as a graph embedded on the surface (where each face is a quadrilateral), the ideal quadrilateral meshes are structured meshes where each interior vertex (i.e. a vertex not on the boundary on the mesh) belongs to 4 quadrilaterals and each boundary vertex belongs to 3 quadrilaterals. However, sometimes it is not possible to do so and one may be required to introduce extraordinary vertices that violate this condition. The natural problem then arises, how one can partition such an unstructured mesh into structured submeshes. This partitioning problem is of interest in the areas of mesh compression, mesh isomporphism and texture mapping. In [1], Eppstein et. al. demonstrate how to partition quadrilateral meshes into structured submeshes using motorcycle graphs [3, 2]. If such a partition is represented using a schematic partition, they show that for bounded genus graphs the number of vertices, edges and faces of the schematic partition for the motorcycle graph is at most 24 times the optimal such schematic partition. They also show that computing an optimal schematic partition is NP-hard. They leave open several problems out of which we propose to investigate the following