Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they share a common neighbour on the right; we form the other graph similarly from the vertices on the right.

This pops up, for example, when finding collaboration relationships in a bipartite graph from scientists to papers or actors to movies.

This being a common problem, I wonder if it has a common name, and maybe specific literature on it.

  • $\begingroup$ OK, thanks for the clarification of what you're trying to achieve. Now I don't understand what the problem is. It seems entirely straightforward to construct those two graphs. It's a straightforward programming exercise (just loop over vertices, etc.). What are you unsure about? What's wrong with the obvious way of constructing those two graphs? Why do you want a name/literature? What are you going to do with a name/literature? $\endgroup$
    – D.W.
    Commented Aug 18, 2016 at 20:30
  • $\begingroup$ @D.W. Seems to be a straight-forward reference request to me? $\endgroup$
    – Raphael
    Commented Aug 18, 2016 at 21:57
  • $\begingroup$ Which @saltthehash did provide $\endgroup$ Commented Aug 18, 2016 at 21:59

2 Answers 2


You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.

  • $\begingroup$ Extremely useful. $\endgroup$ Commented Aug 19, 2016 at 0:40

It would just be an example of a graph partitioning problem. Here is a link to a paper on partitioning bipartite graphs: https://arxiv.org/pdf/cs/0108018.pdf

  • $\begingroup$ Thanks for the answer. However, given the clarifications to the question, it appears this answer is no longer correct/relevant. Does that sound right to you? If it does, I'd suggest deleting it, to avoid clutter. I realize it's a bit annoying to answer an unclear question and have your time turn out to have been wasted -- my sympathies on that. $\endgroup$
    – D.W.
    Commented Aug 18, 2016 at 20:31
  • $\begingroup$ The link saltthehash posted is relevant. I don't think this should be deleted. $\endgroup$ Commented Aug 18, 2016 at 21:35
  • $\begingroup$ @RodrigoStv, I don't understand. That paper does not construct a graph following the way that you requested in your updated question. Your question specifies a particular way of constructing the two graphs, which isn't the same as the way the paper describes. Perhaps the question needs to be revised to clarify what you are looking for? I'm terribly confused about what's going on here. $\endgroup$
    – D.W.
    Commented Aug 18, 2016 at 22:51
  • $\begingroup$ I was Just looking for an initial reference on anything related to the problem i described. Maybe i should review the question. But id say that terribly confused is a stretch. $\endgroup$ Commented Aug 18, 2016 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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