Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Question

Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Given an undirected graph G, is there another graph, H, such that:

• all vertices of G are in H
• H is allowed extra vertices not in G
• if a and b are connected in G, a and b are also connected in in H (possibly with at least some of the extra vertices in the H path from a to b)
• if c and d are not connected in G, c and d are not connected in H
• each vertex in H has degree at most 3
• the edges of H can be enumerated in logspace given an input G

Maybe this could be called a logspace reduction of G to a graph that has max degree of 3 that preserves connectivity?

Answer 1

For each edge $(u,v)$ in $G$, add vertices $w_{u,v}$ and $w_{v,u}$ to $H$, and add the edge $(w_{u,v},w_{v,u})$ to $H$.

For each vertex $u$ in $G$, if $u$ has edges $(u,v_1),\dots,(u,v_k)$, then add edges $(w_{u,v_i},w_{u,v_{i+1}})$ and $(u,w_{u,v_1})$ to $H$; and add edges $(w_{v_i,u},w_{v_{i+1},u})$ and $(w_{v_1,u},v)$ to $H$.

I believe this $H$ satisfies all of your properties. Also, I believe it can be constructed in logspace (please check me and verify for yourself).