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.