# zbMATH — the first resource for mathematics

ILIGRA: an efficient inverse line graph algorithm. (English) Zbl 1347.05239
Summary: 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.

##### MSC:
 05C85 Graph algorithms (graph-theoretic aspects) 05C76 Graph operations (line graphs, products, etc.) 68Q25 Analysis of algorithms and problem complexity
##### Keywords:
graph algorithm; line graph; root graph
ILIGRA; LEDA
Full Text:
##### References:
  Ahn, YY; Bagrow, JP; Lehmann, S., Link communities reveal multiscale complexity in networks, Nature, 466, 761-764, (2010)  Barabási, AL; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223  Bollobás, B.: Random Graphs. Cambridge University Press, Cambridge (2001) · Zbl 0979.05003  Cauchy, A.L.: Cours d’analyse de l’Ecole Royale Polytechnique, vol. 3 (1821). Imprimerie royale, Paris (reissued by Cambridge University Press), Cambridge (2009) · Zbl 1205.26006  Cvetković, D., Rowlinson, P., Simić, S.: Spectral Generalizations of Line Graphs. Cambridge University Press, Cambridge (2004) · Zbl 1061.05057  Degiorgi, D.G., Simon, K.: A dynamic algorithm for line graph recognition. In: Proceedings of 21st International Workshop on Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science 1017), pp. 37-48. Springer-Verlag (1995)  Erdős, P.; Rényi, A., On random graphs, I, Publ. Math. (Debr.), 6, 290-297, (1959) · Zbl 0092.15705  Evans, T., Lambiotte, R.: Line graphs, link partitions, and overlapping communities. Phys. Rev. E 80(1), 016105 (2009)  Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities, 2nd edn. Cambridge University Press, Cambridge (1988)  Krausz, J., Démonstration nouvelle d’un théorème de Whitney sur les réseaux, Mat. Fiz. Lapok, 50, 75-85, (1943) · Zbl 0061.41401  Krawczyk, MJ; Muchnik, L.; Manka-Krason, A.; Kulakowski, K., Line graphs as social networks, Phys. A, 390, 2611-2618, (2011)  Lehot, PGH, An optimal algorithm to detect a line graph and output its root graph, J. ACM, 21, 569-575, (1974) · Zbl 0295.05118  Manka-Krason, A.; Kulakowski, K., Assortativity in random line graphs, Acta Phys. Pol. B Proc. Suppl., 3, 259-266, (2010)  Manka-Krason, A.; Mwijage, A.; Kulakowski, K., Clustering in random line graphs, Comput. Phys. Commun., 181, 118-121, (2010) · Zbl 1202.05129  Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999) · Zbl 0976.68156  Nacher, JC; Ueda, U.; Yamada, T.; Kanehisa, M.; Akutsu, T., Line graphs as social networks, BMC Bioinfo., 24, 2611-2618, (2004)  Nacher, JC; Yamada, T.; Goto, S.; Kanehisa, M.; Akutsu, T., Two complementary representations of a scale-free network, Phys. A, 349, 349-363, (2005)  Naor, J.; Novick, MB, An efficient reconstruction of a graph from its line graph in parallel, J. Algoritm., 11, 132-143, (1990) · Zbl 0715.68070  Ore, O.: Theory of Graphs, vol. 21. American Mathematical Society Colloquium Publications (1962) · Zbl 0105.35401  Roussopoulos, ND, A maxm,n algorithm for detecting the graph h from its line graph g, Info. Process. Lett., 2, 108-112, (1973) · Zbl 0274.05116  Simić, S., An algorithm to recognize a generalized line graphs and ouput its root graph, Publ. Math. Inst. (Belgrade), 49, 21-26, (1990)  Van Mieghem, P.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2011) · Zbl 1232.05128  Rooij, ACM; Wilf, HS, The interchange graph of a finite graph, Acta Math. Acad. Sci. Hung., 16, 263-269, (1965) · Zbl 0139.17203  Whitney, H., Congruent graphs and the connectivity of graphs, Am. J. Math., 54, 150-168, (1932) · Zbl 0003.32804
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.