The Maximum Rectilinear Crossing Number of the Petersen Graph

Authors

Elie Feder, CUNY Kingsborough Community CollegeFollow
Heiko Harborth, Technische Universitat Braunschweig
Steven Herzberg, Rambam Mesitva High School
Sheldon Klein, Cooper Union for the Advancement of Science and Art

Document Type

Article

Publication Date

2010

Abstract

We prove that the maximum rectilinear crossing number of the Petersen graph is 49. First, we illustrate a picture of the Petersen graph with 49 crossings to prove the lower bound. We then prove that this bound is sharp by carefully analyzing the ten Cs's which occur in the Petersen graph and their properties.

Comments

This work was originally published in Congressus Numerantium.