# Is there a name for the problem of turning a bipartite graph into two graphs?

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.

• 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?
– D.W.
Aug 18, 2016 at 20:30
• @D.W. Seems to be a straight-forward reference request to me? Aug 18, 2016 at 21:57
• Which @saltthehash did provide Aug 18, 2016 at 21:59

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.

• Extremely useful. 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

• 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.
– D.W.
Aug 18, 2016 at 20:31
• The link saltthehash posted is relevant. I don't think this should be deleted. Aug 18, 2016 at 21:35
• @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.
– D.W.
Aug 18, 2016 at 22:51
• 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. Aug 18, 2016 at 22:53