By means of character theory and symmetric functions, D. M. Jackson and T. I. Visentin (1990, Trans. Amer. Math. Soc. 322, (343-363)) proved the existence of certain bijections between the set of quadrangulations in orientable surfaces and decorated maps (with marked edges and coloured vertices) in orientable surfaces. The bijections preserve a weight function consisting of a pair Γ°g; nΓ of integer parameters. For quadrangulations, g is the genus and n is the number of faces. For decorated maps, g is the genus plus half the number of white vertices and n is the number of edges. The Quadrangulation Conjecture concerns the problem of finding a natural bijection of this type. Tutte's medial construction is a solution in the special case g ΒΌ 0 of planar maps. We give a construction of a bijection * X X which both extends Tutte's medial construction to non-planar maps and preserves the parameter n of the Quadrangulation Conjecture. (The parameter g is not generally preserved, except when g ΒΌ 0:) Non-orientable surfaces play an important part in the construction of * X X: As part of the construction, we introduce a bijection between orientable rooted quadrangulations and locally orientable, bipartite, rooted quadrangulations.