On the genus of the complete tripartite graph $K_{n,n,1}$

Abstract

For even $n$ we prove that the genus of the complete tripartite graph $K_{n,n,1}$ is $\lceil (n-1)(n-2)/4\rceil$. This is the least number of bridges needed to build a complete $n$-way road interchange where changing lanes is not allowed. Both the theoretical result, and the surprising link to modelling road intersections are new.

15 pages, 6 figures