Cycle cover for structured graph

Question

Consider the undirected graph $G=(V,E)$ example below. More precisely, the vertices in $V$ are labelled with $(x,y)$-coordinates and there is an edge between every vertices sharing the same $x$ and $y$ (not shown on the figure). For instance: $(1,1)-(1,2)$, $(1,1)-(1,3)$ and $(1,1)-(1,4)$

First question: Does this graph structure has a name? Note that the sketch is only an example and can be generalized, but I am not sure whether the generalized graphs would still be planar.

(1,1) --- (1,2) --- (1,3) --- (1,4)
  |         |         |         |
  |         |         |         |
  |         |         |         |
(2,1) --- (2,2)       |         |
  |         |         |         |
  |         |         |         |
  |         |         |         |
(3,1) --- (3,2) --- (3,3) --- (3,4)
  |         |          
  |         |          
  |         |          
(4,1) --- (4,2)

Second question: I'm interested in finding short-cycle covers of this graph (length 4 or 6 typically). Two solutions of the problem for cycles of length 4 would be:

(1,1)-(1,2)-(2,1)-(2,2)
(3,1)-(3,2)-(4,1)-(4,2)
(1,3)-(1,4)-(3,3)-(3,4)

and

(1,1)-(1,3)-(3,1)-(3,3)
(1,2)-(1,4)-(3,2)-(3,4)
(2,1)-(2,2)-(4,1)-(4,2)

And one solution for cycles of length 6:

(1,1)-(2,1)-(2,2)-(3,2)-(3,4)-(1,4)
(1,2)-(1,3)-(3,3)-(3,1)-(4,1)-(4,2)

I know that the general case for 3-cycle cover is NP-complete, but does the special structure of this graph enables to get a simple algorithm solving the cycle cover problem?

Answer 1

Re your first question, re whether this type of graph has a name: it is the line graph of a bipartite graph (the bipartite graph that has a vertex for each nonempty row or column and an edge for each point). Line graphs of bipartite graphs are an important subclass of the perfect graphs. They are generally not planar (e.g. if you have five points on the same row or column you get a $K_5$ subgraph).