1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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.) $\endgroup$ – Marzio De Biasi May 20 '16 at 12:59
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.