A graph that can be embedded in the plane without any edges crossing. Linear-time algorithms were discovered by Hopcroft and Tarjan in 1974.