Most people first meet graphs as a childhood activity; a page of numbered dots, a pencil, and a hidden picture that appears once the lines are drawn. For Isaac Reiter, a fifth-year doctoral student in mathematics at Lehigh, that simple idea has become the foundation of a dissertation.
Reiter's research focuses on a specific family of graphs called interval graphs. The idea starts with the number line. An interval is simply a continuous stretch of it, such as everything between one and three. Give each interval a name, represent it with a dot, and connect two dots whenever their intervals intersect. The result is a compact picture of which intervals interact and which do not.
With three intervals, the picture is easy to read. With 100, it becomes a quick way to take in a large amount of information at a glance.
Reiter works with a more detailed, nuanced version of this idea. Intervals can relate to each other in two ways. They can partially overlap, or one can sit entirely inside another. A standard interval graph cannot tell those two situations apart. So Reiter's graphs color the edges, with one color marking overlap and another marking containment, which adds a layer of information to the picture.
Going from intervals to a colored graph is straightforward. Reiter's research asks what happens when you go the other direction.
Spotlight Recipient
Isaac Reiter
Ph.D. Candidate