Material Insights · Understanding the Material World

Graph theory: Technologies

Technologies

The technologies that rely on it, and how each one uses it

Relied on by 8
  • TCP Internet (TCP/IP) Link-state routing describes the network as a directed graph, and each router builds a tree of shortest paths with itself as root [8].
  • Pkt Packet switching Baran's design treated a network as nodes and links and compared how well distributed and centralised layouts keep working, using the ratio of links to nodes as a measure [10].
  • WWW World Wide Web Pages and their hyperlinks form a link graph, and Brin and Page built maps with as many as 518 million links [9].
  • Srch Web search engine PageRank passes weight along the link structure of the web, which Brin and Page called a citation (link) graph [9].
  • SoM Social media platform A social network is a graph of people and the links between them.
  • RH Ride-hailing platform The road map is stored as a graph of junctions and streets, and route and arrival-time estimates are shortest-path searches on it.
  • LEO Low Earth orbit broadband constellation The fleet is a network whose links change as satellites move, so routing traffic is a problem of paths through a changing graph.
  • Swm Autonomous drone swarms The links between drones form a network of nodes and links, the kind of structure graph theory studies.

as of 2026-11-12

Sources

  1. OSPF Version 2 (RFC 2328) Internet Engineering Task Force (J. Moy), 1998
  2. The Anatomy of a Large-Scale Hypertextual Web Search Engine Sergey Brin and Lawrence Page, Stanford University (copy hosted by the University of Pennsylvania)
  3. On Distributed Communications: I. Introduction to Distributed Communications Networks RAND Corporation (Paul Baran), 1964