Efficient Direct Reconstruction of Bipartite (Multi)Graphs from Their Line Graphs Through a Characterization of Their Edges

We study the line graphs of bipartite multigraphs, which naturally arise in combinatorics, game theory, and applications such as scheduling and motion planning. We introduce a new characterization of these graphs via valid partial assignments of the edges of the underlying bipartite multigraph to the vertices of its line graph. We show that an empty assignment extends to a complete one precisely when the graph is a line graph of a bipartite multigraph. Based on this, we design an O(Δ(G)|E(G)|) algorithm that incrementally constructs such assignments. The algorithm also provides a data structure supporting efficient solutions to problems of maximum clique, maximum weighted clique, minimum clique cover, chromatic number, and independence number. For line graphs of bipartite simple graphs these problems become solvable in linear time, improving on previously known polynomial-time results. For general bipartite multigraphs, our method enhances the O(|V(G)|3) recognition algorithm of Peterson and builds on the results of Demaine et al., Hedetniemi, Cook et al., and Gurvich and Temkin.