R, 4342 bytes
function(w,h,a=1)cbind(a<-1:(h*w-1))cbind(a,a+w^!a%%w)
Creates the spanning graph
1-2-3
|
4-5-6
|
7-8-9
Node i
is connected to node i+1
in general, or to node i+w
if i
is a multiple of w
. This corresponds to a connecting node i
to node i+w^d
where d=1
if i
is a multiple of w
, and d=0
otherwise.