Petersen se interesó en diversas áreas de las matemáticas, tales como geometría, análisis complejo, teoría de números, física matemática, economía matemática, criptografía y teoría de grafos.

Su famoso artículo Die Theorie der regulären graphs[1]​ ("De la teoría de los grafos regulares") significó una contribución fundamental para la teoría de grafos moderna.

En 1898, presentó un contraejemplo para el aclamado teorema de Tait sobre factorabilidad-1 de grafos 3-regulares, que actualmente se conoce como el "grafo de Petersen".

Publicó un tratado sistemático de construcciones geométricas (usando regla y compás) en 1880.

Se le dedicó una edición especial de la revista Discrete Mathematics por el 150.º aniversario de su nacimiento, que incluyó una detallada biografía del matemático conmemorado.