<p>Re your first question, re whether this type of graph has a name: it is the <a href="https://en.wikipedia.org/wiki/Line_graph" rel="nofollow">line graph</a> 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).</p>

CC BY-SA 3.0
2016-05-21T14:22:04.727Z
2016-05-21T14:22:04.727Z
David Eppstein
<p>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$ (<strong>not shown on the figure</strong>). For instance: $(1,1)-(1,2)$, $(1,1)-(1,3)$ and $(1,1)-(1,4)$</p>

<p><strong>First question:</strong> 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.</p>

<pre><code>(1,1) --- (1,2) --- (1,3) --- (1,4)
  |         |         |         |
  |         |         |         |
  |         |         |         |
(2,1) --- (2,2)       |         |
  |         |         |         |
  |         |         |         |
  |         |         |         |
(3,1) --- (3,2) --- (3,3) --- (3,4)
  |         |          
  |         |          
  |         |          
(4,1) --- (4,2)
</code></pre>

<p><strong>Second question:</strong> 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:</p>

<pre><code>(1,1)-(1,2)-(2,1)-(2,2)
(3,1)-(3,2)-(4,1)-(4,2)
(1,3)-(1,4)-(3,3)-(3,4)
</code></pre>

<p>and</p>

<pre><code>(1,1)-(1,3)-(3,1)-(3,3)
(1,2)-(1,4)-(3,2)-(3,4)
(2,1)-(2,2)-(4,1)-(4,2)
</code></pre>

<p>And one solution for cycles of length 6:</p>

<pre><code>(1,1)-(2,1)-(2,2)-(3,2)-(3,4)-(1,4)
(1,2)-(1,3)-(3,3)-(3,1)-(4,1)-(4,2)
</code></pre>

<p>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? </p>

CC BY-SA 3.0
2016-05-20T12:59:19.537Z
Note that the 3-cycle cover problem is NP-complete only on directed graphs; it is polynomial-time solvable on undirected graphs (see Markus Blaser and Bodo Manthey: Two Approximation Algorithms for 3-Cycle Covers.)
Marzio De Biasi
<graph-theory>
Cycle cover for structured graph
wwjoze
# Cycle cover for structured graph

(Asked by: username_0 on 2016-05-20)

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?

**Tags:** graph-theory
> **Comments:**
> **username_1**: Note that the 3-cycle cover problem is NP-complete only on directed graphs; it is polynomial-time solvable on undirected graphs (see Markus Blaser and Bodo Manthey: Two Approximation Algorithms for 3-Cycle Covers.)  

---

## 1 answers

### Answer by username_2 on 2016-05-21. Score: 1

Re your first question, re whether this type of graph has a name: it is the [line graph](https://en.wikipedia.org/wiki/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).


---

