Introduction and History of Basic Graph Algorithms

History of graphs

A graph is a collection of pairs—pairs of integers, pairs of people, pairs of cities, pairs of stars, pairs of countries, pairs of scientific papers, pairs of web pages, pairs of game positions, pairs of recursive subproblems, and even pairs of graphs. Mirroring is the most common method for visualizing graphs; the underlying objects being paired are usually called vertices or nodes, and the pairs themselves are called edges or arcs, but in fact, the objects and pairs can be anything at all.

Among the earliest examples of graphs are road networks and maps thereof. Roman engineers constructed a network of more than 400 000 km of public roads across Europe, western and central Asia, and northern Africa during the height of the Roman empire. Travelers on the road network would carry itineraries, which were either simple lists or more pictorial representations of the landmarks and distances along various roads. The Tabula Peutingeriana, a 13th-century scroll depicting the entire Roman cursus publicus, is widely believed to be a medieval copy of a 5th-century revision of a 1st-century itinerarium pictum, commissioned during the reign of Augustus Caesar. The Peutinger Table is not a geographically accurate map—historians debate whether it qualifies as a map at all!—but an abstract representation of the road network, similar to a modern subway map. Cities along each road are indicated by kinks in the curve representing that road; the names of these cities and the lengths of road segments between them are also indicated on the map. Thus, the map contains enough information to find the shortest route between any two cities in the 5th-century Roman empire. See the figure below, which contains a small excerpt of Konrad Miller’s 1872 restoration of the Tabula Peutingeriana, showing the Roman road from modern-day Birten (Veteribus, top left) through Köln (Agripina) and Bonn (Bonnae) to Mainz (Mogontiaco, top right), with branches to Trier (Avg Tresvirorvm, center) and Metz (Matricorvm, bottom center).