Talk in NYU CG seminar 4/4/23.

A penny graph is the intersection graph of a packing of circles of diameter 1. These graphs, also called minimum-distance graphs, were introduced by Erdös in 1946, who asked for the maximum possible number of edges in a penny graph with n vertices. This problem was fully solved by Harborth in 1974, who in turn introduced the more general notion of a matchstick graph. A matchstick graph is a plane graph drawn with straight-line segments of unit length. Harborth conjectured in 1986 that the same maximum number of edges occurs for matchstick graphs as for penny graphs. I will discuss this conjecture, recently solved, and a number of related unsolved extremal problems.

Joint work with Jérémy Lavollée.