4-regular graph with every edge lying in a unique 4-cycle What are all 4-regular graphs such that every edge in the graph lies in a unique-4 cycle?
Among all such graphs, if we impose a further restriction that any two 4-cycles in the graph have at most one vertex in common, then can we characterize them in some way?
When is it possible to draw such a graph on a plane such that every 4-cycle is of the form: (a,c)-(b,c)-(b,d)-(a,d)-(a,c) for some a,b,c,d ?
 A: There should be lots of these, even with the second condition. So many that I can't imagine a classification. I'll call a $4$-cycle a square.
One construction is as follows: Start with an appropriate connected graph such that 


*

*Each edge is on a unique square 

*All vertices have degree $2$ or $4$. 

*Two $4$-cycles have at most one vertex in common. 


Then identify various degree $2$ vertices in pairs without making any new squares. So appropriate means you can do this. For example take an $N$ cycle for $N$ not too small, and attach a square to each edge. You could even take several of these and glue them together at vertices (in a sort of tree structure.) Here is a $12$-cycle decorated with squares and an extra square glued on just to show that we could grow this out in a wild variety of ways. I think in my identification of degree two vertices I did not create any new squares.

The examples below are included because they look nice and are already in the comments. The graph at the top right meets my three conditions if the two red edges are deleted. I am confident that the degree $2$ vertices could be identified in pairs without creating any new $4$-cycles. 
With the red edges one has four vertices of degree $3$ along with two edges not in a square. One could take a mirror image of that graph and add $4$ more edges to connect them, create two more squares and bring the degrees up (there are also easier remedies such as using two more edges to make a square with the red ones.)
I previously had a claim about the graph with the octagons which was too optimistic.It has $42$ edges missing and I won't specify how to draw them. In each half (ignoring the two curved edges) there are $22$ deficient edges which do not belong to a square and connect vertices of degree $3.$  I thought that one could connect corresponding degree $3$ vertices in each half. I now see that that would put the edge $AD$ on the left into two squares.  I've indicated a different match for edge $CD$ and imagine that it is not hard, with a little care,  to match up deficient edges on the left with those on the right to create just enough squares. I don't think one needs to preserve orientation.  The bottom (fragment of a) graph could probably be treated similarly. One could even try to match up deficient edges without adding any new vertices. 
A: The number of vertices $n$ must be even or the number of 4-cycles is not an integer.  The number of simple connected quartic graphs with the first condition is 0 for $n<12$ and $2,4,25,459$ for $n=12,14,16,18$.  One of those on 12 vertices is the cuboctahedron.  
After the cuboctahedron, the next 3-connected planar quartic graph with the first property has 20 vertices and there are 2 with 24 vertices.
This construction may be useful: A quartic graph with $n$ vertices and the first property has $n/2$ 4-cycles.  Make a new graph $H$ with the 4-cycles of $G$ as vertices and an edge wherever two 4-cycles meet at a vertex.  You get a quartic multigraph with half the number of vertices, simple if $G$ also satisfies the second property.  To get back from $H$ to $G$ you need to choose a cyclic order of the edges around each vertex, which is similar to embedding it on an orientable surface except that reversing the order at some vertices doesn't change the result.  This operation is related to the medial graph construction.  It would probably not be hard to characterise when the medial graph of an embedded quartic graph has the required properties.
A: Consider two labeled squares, vertices on one labeled from the abcd alphabet, the other labeled
from 1234.  We are going to identify one or more pairs of vertices while maintaining the constraint
that induced edges are not identified as well as not identifying vertices labeled from the same alphabet.
It is clear that there are 16 ways to make one pair of vertices.  Once one such pair is made,
there are for each pair precisely 4 ways to make a second disjoint pair.  Making a third pair
violates the edge identification condition.  So there are 48 distinct ways (after removing
duplicated efforts) to identify two labeled squares.
The idea now is to make a brute force enumeration extending this to larger sets of squares.
Even if one considers the labels as distinct, it will be a challenge to list those identifications that
do not induce additional four-cycles.  Further, even with software to figure out isomorphism
types, I think the number of such types will be exponential in the number of squares, if not
doubly exponential, as it seems to me to be enumerating certain 4-designs.
A: Here is one more construction which covers a lot of graphs: start with a $4$-regular graph with girth at least $5$, take the line graph and delete a perfect matching in each resulting $K_4$...
This may get us almost all answers to the second question:
If we start with an answer to the second question, and "fill in" all squares to make $C_4$s, we end up with a line graph of a $4$-regular graph. Not necessarily girth greater $3$, though.
To get all such graphs this way, you need to start with any $4$-regular graph, take the line graph, and then carefully delete the matchings to avoid extra squares. Describing what "carefully" entails, and deciding if it is even possible, may turn out to be difficult, though.
A: As a matter of fact, I have encountered this family of 4-regular graphs, where every edges lies in exactly one C4, and no two C4 share more than one vertex.
You obtain any such graph with the following operation:
 - begin with any 3-regular graph G of girth at least 5, together with a perfect matching M.
 - Construct the graph H whose vertices are E(G)\M, and connect the pairs which cover a given edge of the matching M (so at distance exactly 2, linked by an edge of M). The graph H has the desired property, and you can reach any graph with this property with a well chosen G and M.
I now have a further question: What is the maximum possible (fractional) chromatic number of the square of such a graph? Could it be at most 8, possibly when the incidence graph of the C4's has sufficiently large girth?
