"Bridges to Networks: The Journey of Graph Theory from Mathematical Abstraction to Real-World Impact"
Article Sidebar
Main Article Content
Abstract: Graph theory has evolved from its origins in Euler’s 1736 solution to the Königsberg bridge problem into a foundational discipline with far-reaching applications in computer science, biology, social networks, and artificial intelligence. This literature review systematically examines the field’s historical development, theoretical advancements, algorithmic breakthroughs, and modern applications. Key contributions include Euler’s foundational work on graph traversability, Ramsey’s combinatorial insights, Erdős and Rényi’s random graph theory, and contemporary developments in complex networks (Watts-Strogatz, Barabási-Albert) and spectral methods (Chung). The review also highlights pivotal algorithmic contributions (Tarjan’s DFS, Johnson’s shortest paths) and real-world applications in machine learning (Zhou et al.), network science (Newman), and infrastructure optimization. Emerging trends such as dynamic graphs, graph neural networks (GNNs), and quantum graph algorithms are identified as critical future directions. By synthesizing classical and modern research, this review underscores graph theory’s enduring relevance in modeling and analyzing interconnected systems across disciplines.
Downloads
References
Albert, R., & Barabási, A.-L. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.
Bollobás, B. (2001). Random graphs (2nd ed.). Cambridge University Press.
Chung, F. R. K. (1997). Spectral graph theory. American Mathematical Society.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Diestel, R. (2005). Graph theory (3rd ed.). Springer.
Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8, 128–140.
Even, S., & Tarjan, R. E. (1976). Network flow and testing graph connectivity. SIAM Journal on Computing, 4(4), 507–518.
Honnuraswamy Y, P. K. C. (2024). Assessing the performance of online education apps: Implications on students' understanding ability. EPRA International Journal of Multidisciplinary Research (IJMR), 10(2), 349–354.
Harary, F. (1969). Graph theory. Addison-Wesley.
Hopcroft, J., & Tarjan, R. E. (1973). Efficient algorithms for graph manipulation. Communications of the ACM, 16(6), 372–378.
Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1), 1–13.
Lovász, L. (1993). Random walks on graphs: A survey. Combinatorics, Paul Erdős is eighty, 2, 1–46.
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45(2), 167–256.
Dr. Honnuraswamy, Y., & Dr. Prashanth, K. C. (2025). Developing applying ability through mobile learning: How education apps enhance practical skills in Kalyana Karnataka. EPRA International Journal of Economics, Business and Management Studies (EBMS), 12(4). https://doi.org/10.36713/epra21037
Ramsey, F. P. (1930). On a problem of formal logic. Proceedings of the London Mathematical Society, 30(4), 264–286.
Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160.
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440–442.
West, D. B. (2001). Introduction to graph theory (2nd ed.). Prentice Hall.
Erdős, P., & Rényi, A. (1959). On random graphs. Publicationes Mathematicae, 6, 290–297.
Gross, J. L., & Yellen, J. (2005). Graph theory and its applications (2nd ed.). Chapman & Hall/CRC.
Bondy, J. A., & Murty, U. S. R. (2008). Graph theory. Springer.
Chartrand, G., & Lesniak, L. (2004). Graphs & digraphs (4th ed.). Chapman and Hall/CRC.
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in our journal are licensed under CC-BY 4.0, which permits authors to retain copyright of their work. This license allows for unrestricted use, sharing, and reproduction of the articles, provided that proper credit is given to the original authors and the source.