ILIGRA: an efficient inverse line graph algorithm. This paper presents a new and efficient algorithm, Iligra, for inverse line graph construction. Given a line graph H, Iligra constructs its root graph G with the time complexity being linear in the number of nodes in H. If Iligra does not know whether the given graph H is a line graph, it firstly assumes that H is a line graph and starts its root graph construction. During the root graph construction, Iligra checks whether the given graph H is a line graph and Iligra stops once it finds H is not a line graph. The time complexity of Iligra with line graph checking is linear in the number of links in the given graph H. For sparse line graphs of any size and for dense line graphs of small size, numerical results of the running time show that Iligra outperforms all currently available algorithms.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element