Generating \(3\)-Connected Quadrangulations on Surfaces

Abstract

Let \(G\) be a simple quadrangulation on a closed surface \(F^2\). Two reductions for quadrangulations are defined in this paper: face-contraction and \(4\)-cycle removal. We define four types of irreducibility:

1. \(G\) is \({irreducible}\) if any face-contraction breaks the simplicity of \(G\).
2. \(G\) is \(\mathcal{D}_3\)-\({irreducible}\) if \(G\) has minimum degree at least 3 and any face-contraction or 4-cycle removal breaks simplicity or reduces minimum degree to less than 3.
3. \(G\) is \(\mathcal{K}_3\)\({-irreducible}\) if \(G\) is 3-connected and any face-contraction or 4-cycle removal breaks simplicity or 3-connectedness.
4. \(G\) is \(\mathcal{S}_4\) \({-irreducible}\) if \(G\) has no separating 4-cycle and any face-contraction breaks simplicity or creates a separating 4-cycle.

In [7] that, except for the sphere and projective plane, irreducibility and \(\mathcal{D}_3\)-irreducibility of quadrangulations are equivalent. In this paper, we prove that for all surfaces, \(\mathcal{D}_3\)-irreducibility and \(\mathcal{K}_3\)-irreducibility are equivalent. Additionally, we prove that for the sphere, projective plane, and torus, \(\mathcal{D}_3\)-irreducibility and \(\mathcal{S}_4\)-irreducibility are equivalent, but this does not hold for surfaces of high genus.