1986 · Theory & algorithms

Giving structure to a graph

Efficient graph algorithms reveal relationships without repeatedly exploring everything.

John Hopcroft · Robert Tarjan

1986Turing Award

Visual guide

The prize, pictured

Open full-size ↗Download poster ↓中文版海报 ↗

Giving structure to a graph: Efficient graph algorithms reveal relationships without repeatedly exploring everything. — Original AI-generated infographic by Curionode. Read the text version below for the full explanation.

Read the poster text

Explore
Traverse vertices and edges.
Record
Keep useful structural information.
Decide
Use that structure to solve a problem.

Graph algorithms support tasks across compilers, networks and optimisation, where relationships matter as much as individual objects.

A graph is an abstraction; an algorithm’s guarantees depend on the precise problem and representation.

01 · The idea

In everyday language

John Hopcroft and Robert Tarjan advanced the design and analysis of algorithms and data structures. Their work showed how the structure uncovered during a graph traversal could support powerful procedures, including tests of whether a graph can be drawn without crossings. The organisation of the computation was as important as its individual operations.

Why it matters

Graph algorithms support tasks across compilers, networks and optimisation, where relationships matter as much as individual objects.

02 · The people

Who brought the idea to life?

John Hopcroft

John Hopcroft helped establish algorithm design and analysis as a systematic discipline. His work on automata, graph algorithms, and data structures showed how mathematical insight could produce substantial efficiency improvements. With Robert Tarjan he developed influential methods for graph problems; he also co-authored widely used textbooks. At Cornell, his research and teaching helped turn algorithms into a coherent core of computer science education.

Read the biography ↗

Robert Tarjan

Robert Tarjan developed powerful graph algorithms and data structures together with precise methods for analyzing their efficiency. His research includes depth-first search techniques, union-find analysis, and self-adjusting data structures. Collaborations with John Hopcroft helped establish efficient graph processing as a fundamental area of algorithms. At the time of the 1986 award, he was affiliated with Princeton University and AT&T Bell Laboratories.

Read the biography ↗

03 · Read further