Can the topology of a quad mesh with irregular vertices be represented as a square grid graph?

Question

I would like to know whether the topology of a quad mesh containing irregular vertices (vertices of degree higher or lower than 4) can be represented as a square grid graph or not.

Ideally I would like to find (or build) an algorithm that takes a quad mesh in input and computes its topological representation as a 2D array.

For clarity I have made this example where I tried to depict the adjacency relations between the faces of a quad mesh with irregular vertices inside a regular 2D grid.

Provided this representation is correct:

• Do you think it can be generalized to other quad meshes with irregular vertices ?
• If so, would there be a name for it ?
• If so, would there be an algorithm to compute it ? (related to graph theory maybe ?)

note: this question was first asked on SO but I was suggested to post/move it here as Math SE seems to be more appropriate for this kind of topic.

Answer 1

Of course, this can only work if the mesh is homeomorphic to a plane (and not, say, to a torus or a monkey head) to begin with.

But otherwise, this seems to follow by induction as in the following sketch: Remove one quad with with at least one boundary edge, build a square grid for the rest; add squares representing the removed quad to the correct neighbours and perhaps "extrude" a few boundary squares to make the grid rectangular again.