---------- Forwarded message ---------- Date: Sun, 24 Oct 1999 09:46:05 -0700 (PDT) From: Bill Thurston 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