---------- Forwarded message ----------
Date: Sun, 24 Oct 1999 09:46:05 -0700 (PDT)
From: Bill Thurston <wpt@math.ucdavis.edu>
To: math-fun@optima.CS.Arizona.EDU
Subject: Genus of freeway interchanges

Suppose you need to design a freeway interchange from which there
are n outgoing directions.  Traffic must be able to go from any     
incoming direction to any different outgoing direction, and the interchange 
must be designed so that the lanes going in the different outgoing
directions are sorted out (by carefully reading and obeying the signs!)
before they enter the interchange, and they do not cross within the
interchange.  Thus, the clover-leaf interchanges which used to be
the standard design where two freeways cross, are not allowed ---
as it turns out, they are dangerous, because traffic entering
from one leaf of the clover must cross traffic that exits
another leaf of the clover in too short a space.

What is the minimum number of overpasses needed to implement these
constraints for n outgoing directions, or equivalently,
what is the minimum genus oriented surface on which the connections can
be made without crossings?  I'm only sure of the answers for the
two most common types, n = 3 and n = 4 --- it's a fun puzzle that I won't
spoil.  As those of you familiar with examples like the "Maze" of
approaches to the San Franisco Bay bridge from the east,  the minimal genus
seems to grow quickly (apparently quadratically) with n.  A lower bound
is the minimum genus embedding for the complete bipartite graph K(n,n) ---
does someone know the results for this?

        --Bill Thurston