Graph Theory & Network Science: Seven Bridges to Complex Networks
Encyclopedia/1. The Cosmos & The Natural World/1. Mathematics & Formal Systems/09. Graph Theory & Network Topology • Curated by Admin Timeline.sg
Graph theory and network science trace their origins to Euler's 1736 solution of the Seven Bridges of Königsberg problem, evolving through Hamiltonian circuits, the Four Color Theorem, random graphs, small-world networks, and scale-free topology, with applications across mathematics, physics, biology, and social sciences.
Chronological Storyline (47 Milestones)
1736 CE
Euler Solves Seven Bridges of Königsberg
Leonhard Euler publishes a paper solving the Königsberg bridge problem, founding graph theory. He models landmasses as vertices and bridges as edges, proving that a walk crossing each bridge exactly once is impossible. #graphTheory #mathematics
Euler Solves Seven Bridges of Königsberg By Twotwos - Own work based on: Konigsberg bridges.png. This file was derived from: Image-Koenigsberg, Map by Merian-Erben 1652.jpg, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=175193733
1750 CE
Euler's Formula for Polyhedra
Euler discovers the formula V - E + F = 2 for convex polyhedra, linking vertices, edges, and faces. This foundational result later influences graph theory and topology. #graphTheory #topology
1847 CE
Kirchhoff's Circuit Laws
Gustav Kirchhoff formulates laws for electrical circuits using graph theory concepts. His work introduces the notion of trees and cycles in graphs, influencing network analysis. #graphTheory #electricalEngineering
1852 CE
Four Color Conjecture Proposed
Francis Guthrie conjectures that four colors suffice to color any map so that adjacent regions have different colors. This problem drives graph theory development for over a century. #graphTheory #mathematics
Four Color Conjecture Proposed By Inductiveload - Based on a this raster image by chas zzz brown on en.wikipedia., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1680050
1856 CE
Hamiltonian Circuits Defined
William Rowan Hamilton invents the Icosian game, involving finding a cycle visiting each vertex exactly once on a dodecahedron. This introduces Hamiltonian paths and circuits. #graphTheory #mathematics
Hamiltonian Circuits Defined By Eyesinthefire - Own work - adapted from: by User:Janusz.c and styled after: by User:David Eppstein, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=187996031
1878 CE
Sylvester Coins 'Graph' Term
James Joseph Sylvester uses the term 'graph' in a mathematical context, referring to diagrams of chemical structures. This helps formalize graph theory terminology. #graphTheory #mathematics
Sylvester Coins 'Graph' Term By Michel Bakni - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=151762031
1890 CE
Heawood Proves Five Color Theorem
Percy Heawood proves that five colors always suffice for map coloring, correcting a flaw in Kempe's attempted proof of the four color theorem. His work advances graph coloring theory. #graphTheory #mathematics
Heawood Proves Five Color Theorem By Original: Dmharvey Vector: Inductiveload - Own work based on: 4CT Non-Counterexample 1.svg this raster image by Dmharvey on en.wikipedia., Public domain, https://commons.wikimedia.org/w/index.php?curid=1680093
1913 CE
König Publishes First Graph Theory Book
Dénes Kőnig publishes 'Theory of Finite and Infinite Graphs', the first comprehensive textbook on graph theory. It systematizes the field and inspires further research. #graphTheory #mathematics
König Publishes First Graph Theory Book By no conegut - BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM MATEMATIKA INTÉZET: https://math.bme.hu/~hujter/konig1928.jpg, Public domain, https://commons.wikimedia.org/w/index.php?curid=90577639
1928 CE
Ramsey Theory Emerges
Frank Ramsey proves a theorem in combinatorial logic, later known as Ramsey's theorem, which guarantees the existence of order in large graphs. It becomes a cornerstone of graph theory. #graphTheory #combinatorics
1930 CE
Kuratowski's Planar Graph Theorem
Kazimierz Kuratowski characterizes planar graphs by proving that a graph is non-planar iff it contains a subdivision of K5 or K3,3. This is a fundamental result in graph theory. #graphTheory #mathematics
Kuratowski's Planar Graph Theorem By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=23861616
1935 CE
Whitney's Graph Theory Contributions
Hassler Whitney publishes influential papers on graph coloring, matching, and the Four Color Problem. He introduces the concept of the chromatic polynomial. #graphTheory #mathematics
Whitney's Graph Theory Contributions By Sally Thurston, the subject Hassler Whitney's daughter. - Emailed to me by the author., CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=46360725
1941 CE
Brooks' Theorem on Graph Coloring
R. Leonard Brooks proves that for any connected graph, the chromatic number is at most the maximum degree, except for complete graphs and odd cycles. This is a key bound in graph coloring. #graphTheory #mathematics
Brooks' Theorem on Graph Coloring By Vectorisation: BethNaught. Original: Claudio Rocchini (User:Rocchini) - This file was derived from: Graph exact coloring.gif This W3C-unspecified vector image was created with Inkscape ., CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=42831705
1947 CE
Tutte's Contributions to Graph Theory
William Tutte begins publishing seminal work on graph factorization, matroids, and the Tutte polynomial. He also cracks the German Lorenz cipher using graph theory during WWII. #graphTheory #cryptography
1959 CE
Erdős–Rényi Random Graph Model
Paul Erdős and Alfréd Rényi introduce the random graph model G(n,p), where edges are included with probability p. This launches the study of random graphs and probabilistic methods. #graphTheory #randomGraphs
Erdős–Rényi Random Graph Model By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=115108260
1960 CE
Dijkstra's Shortest Path Algorithm
Edsger Dijkstra publishes an algorithm for finding the shortest path between nodes in a graph. It becomes a fundamental tool in network routing and operations research. #graphTheory #algorithms
Dijkstra's Shortest Path Algorithm By Ibmua - Work by uploader., Public domain, https://commons.wikimedia.org/w/index.php?curid=6282617
1962 CE
Kruskal's and Prim's Algorithms
Joseph Kruskal and Robert Prim independently develop algorithms for finding minimum spanning trees in weighted graphs. These are essential for network design. #graphTheory #algorithms
Kruskal's and Prim's Algorithms By Shiyu Ji - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=54420893
1965 CE
Milgram's Small-World Experiment
Stanley Milgram conducts experiments showing that any two people in the US are connected by about six acquaintances, coining 'six degrees of separation'. This inspires small-world network research. #networkScience #sociology
Milgram's Small-World Experiment By Daniel' (User:Dannie-walker) - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=8977072
1969 CE
ARPANET Connects First Nodes
The ARPANET, precursor to the Internet, connects four nodes using packet switching. This network becomes a testbed for graph theory and network protocols. #networkScience #internet
ARPANET Connects First Nodes By ARPANET - The Computer History Museum ([1]), en:File:Arpnet-map-march-1977.png, Public domain, https://commons.wikimedia.org/w/index.php?curid=9990864
1971 CE
Cook-Levin Theorem: NP-Completeness
Stephen Cook and Leonid Levin independently prove that the Boolean satisfiability problem is NP-complete. Many graph problems (e.g., Hamiltonian cycle) are shown to be NP-complete. #graphTheory #computationalComplexity
1972 CE
Karp's 21 NP-Complete Problems
Richard Karp publishes a list of 21 NP-complete problems, including graph problems like vertex cover, clique, and Hamiltonian cycle. This solidifies the importance of graph theory in complexity. #graphTheory #computationalComplexity
1973 CE
Tutte's Perfect Matching Theorem
William Tutte proves a necessary and sufficient condition for a graph to have a perfect matching. This result is fundamental in matching theory and combinatorial optimization. #graphTheory #combinatorics
1976 CE
Four Color Theorem Proved with Computers
Kenneth Appel and Wolfgang Haken prove the Four Color Theorem using computer-assisted case analysis. This is the first major theorem proved with a computer, sparking debate. #graphTheory #mathematics
1981 CE
Graph Minors Theory Initiated
Neil Robertson and Paul Seymour begin a series of papers on graph minors, culminating in the Graph Minors Theorem. This deep theory has profound implications for graph structure and algorithms. #graphTheory #mathematics
1984 CE
PageRank Algorithm Developed
Larry Page and Sergey Brin develop PageRank, a graph-based algorithm for ranking web pages. It uses the link structure of the web and becomes the foundation of Google's search engine. #networkScience #algorithms
PageRank Algorithm Developed By Sage santo - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=153695322
1995 CE
Watts-Strogatz Small-World Model
Duncan Watts and Steven Strogatz publish a model showing that networks with high clustering and short path lengths (small-world) arise from rewiring a regular lattice. This explains many real networks. #networkScience #graphTheory
Watts-Strogatz Small-World Model By The Opte Project - Originally from the English Wikipedia; description page is/was here., CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=1538544
1999 CE
Barabási–Albert Scale-Free Model
Albert-László Barabási and Réka Albert propose the scale-free network model, where new nodes preferentially attach to highly connected nodes. This explains power-law degree distributions in many real networks. #networkScience #graphTheory
2001 CE
Network Motifs Discovered
Ronen Milo and colleagues identify recurring, significant patterns of interconnections (network motifs) in biological and technological networks. This provides a new way to analyze network function. #networkScience #biology
2002 CE
Community Detection Algorithms
Michelle Girvan and Mark Newman propose the Girvan-Newman algorithm for detecting community structure in networks. This sparks extensive research on network clustering. #networkScience #graphTheory
2003 CE
Human Disease Network Mapped
Goh et al. construct a human disease network linking diseases to genes, revealing that many diseases share genetic origins. This applies graph theory to medicine. #networkScience #medicine
2004 CE
Proof of the Graph Minor Theorem
Robertson and Seymour complete their proof of the Graph Minor Theorem, stating that any infinite set of graphs contains one that is a minor of another. This is a landmark in structural graph theory. #graphTheory #mathematics
2005 CE
Social Network Analysis Goes Mainstream
The rise of social media platforms like Facebook and Twitter generates massive social network data. Graph theory becomes essential for analyzing online social networks and influence. #networkScience #socialMedia
2006 CE
Graph Databases Emerge
Neo4j, the first graph database, is released. Graph databases store data as nodes and edges, enabling efficient querying of complex relationships. #graphTheory #databases
2007 CE
Network Science Textbook Published
Albert-László Barabási publishes 'Network Science', a comprehensive textbook that popularizes the field. It becomes a standard reference for students and researchers. #networkScience #education )
2008 CE
GraphX and Graph Processing Frameworks
Apache Spark's GraphX library is developed for large-scale graph processing. This enables graph algorithms to run on distributed computing clusters. #graphTheory #bigData
GraphX and Graph Processing Frameworks By Apache Software Foundation - Vectorised by Vulphere based from https://www.apache.org/logos/res/spark/spark.pdf, Apache License 2.0, https://commons.wikimedia.org/w/index.php?curid=57832155
2010 CE
Deep Learning on Graphs Begins
Researchers start developing graph neural networks (GNNs) for machine learning on graph-structured data. This merges graph theory with deep learning. #graphTheory #machineLearning
2012 CE
Network Medicine Field Established
The field of network medicine formally emerges, using network theory to understand disease mechanisms, drug targets, and personalized medicine. #networkScience #medicine
2013 CE
GraphBLAS Standard Initiated
The GraphBLAS standard is proposed to define a set of building blocks for graph algorithms in terms of linear algebra. This aims to improve performance and portability. #graphTheory #algorithms
GraphBLAS Standard Initiated By Jakab Rokob - https://graphblas.org/, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=103501911
2014 CE
Network Science Recognized as Discipline
The Network Science Society (NetSci) is founded, and academic programs in network science proliferate. The field gains recognition as an interdisciplinary domain. #networkScience #education
2015 CE
Graph Theory in Neuroscience: Connectome
The Human Connectome Project maps neural connections in the brain using graph theory. This reveals network properties like small-world topology and hub nodes. #networkScience #neuroscience
Graph Theory in Neuroscience: Connectome By Xavier Gigandet et. al. - Gigandet X, Hagmann P, Kurant M, Cammoun L, Meuli R, et al. (2008) Estimating the Confidence Level of White Matter Connections Obtained with MRI Tractography. PLoS ONE 3(12): e4006. doi:10.1371/journal.pone.0004006, CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=8134159
2016 CE
AlphaGo Uses Graph Networks
DeepMind's AlphaGo defeats world champion Lee Sedol in Go. The system uses Monte Carlo tree search and neural networks, leveraging graph representations of board positions. #graphTheory #AI
2017 CE
Graph Attention Networks Introduced
Petar Veličković et al. propose graph attention networks (GATs), which use attention mechanisms to weigh neighbor contributions. This becomes a popular GNN architecture. #graphTheory #machineLearning
2018 CE
Graph Theory in Epidemiology: COVID-19
Network models are used to simulate COVID-19 spread, evaluate interventions, and analyze contact tracing. Graph theory becomes crucial for pandemic response. #networkScience #epidemiology
2019 CE
Quantum Graph Theory Advances
Researchers explore quantum algorithms for graph problems, such as quantum walks and graph isomorphism. This opens new frontiers in quantum computing. #graphTheory #quantumComputing
2020 CE
Graph Neural Networks in Drug Discovery
GNNs are applied to molecular graph data for drug discovery, predicting molecular properties and generating new molecules. This accelerates pharmaceutical research. #graphTheory #drugDiscovery
2021 CE
Network Science for Climate Change
Graph theory is used to model climate systems, analyze ecological networks, and design resilient infrastructure. Network science becomes a tool for sustainability. #networkScience #climateChange
2022 CE
Large Language Models and Knowledge Graphs
Integration of large language models (LLMs) with knowledge graphs improves reasoning and factual accuracy. Graph theory enhances AI's ability to represent structured knowledge. #graphTheory #AI
Large Language Models and Knowledge Graphs By Jayarathina - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=37135596
2023 CE
Graph Theory in Quantum Error Correction
Graph states and surface codes are used in quantum error correction. Graph theory provides a framework for designing fault-tolerant quantum computers. #graphTheory #quantumComputing
