The recognition problem for line bigraphs Original Research Article

Given are two graphs H1=(V,E1) and H2=(V,E2) on the same vertex set. The line bigraph is the bipartite graph with the disjoint union of E1 and E2 as vertex set, and an edge between e1∈E1 and e2∈E2 if the edges have some common vertex in V. We first show that the problem to determine whether a given bipartite graph is the line bigraph of two such graphs is NP-complete. We then present two special cases where the question can be solved in polynomial time. A C4-free bipartite graph is a line bigraph if and only if each component of the graph obtained by removing all degree-2 vertices has at most one cycle. Using the intersection multigraph of the set of all large bicliques, we then show that there is an efficient recognition algorithm for recognizing line bigraphs of two graphs both having minimum degree at least 3.