The recognition problem for line bigraphs (Q1398267)

The line bigraph \(G=(E_1^\prime, E_2^\prime,F)\) of two graphs \(H_i=(V,E_i)\), \(i=1,2\), has disjoint copies \(E_i^\prime\) of \(E_i\) as partite sets, and \(\{e_1',e_2'\} \in F\) if \(e_1 \in E_1\) and \(e_2 \in E_2\) share an endpoint in \(V\). It is NP-complete to decide whether a given bipartite graph \(G\) is the line bigraph of suitable graphs \(H_1\) and \(H_2\). This problem becomes solvable in polynomial time if \(G\) is \(C_4\)-free or \(\delta(H_i) \geq 3\) for \(i=1,2\).