Phipps Garden Subway Problem

Written submission is due in lecture on Wednesday, April 11 2012.

I’m updating this post according to the restatement given in lecture on Friday.

You’re given a map of a subway rail system (planar graph). Each face (except the outer one) of the planar graph is a country with a train that travels around it continuously in the clockwise direction.

All vertices are intersections of track of degree 3. Furthermore, the graph is 2-edge-connected, meaning you can’t delete a single edge and disconnect the graph.

Prove that there is a scheduling algorithm that guarantees no gridlocks and no starvation.

No gridlocks means that trains may only travel in one direction on a rail at one time. No starvation means that every train must make infinitely many trips around its face.

If the planar graph is embedded on a sphere, there’s now an outside country that has a train traveling clockwise. Prove that there is no scheduling algorithm.