It turns out that enumeration of graphs embedded on surfaces (an active area of combinatorics since Bill Tutte's pioneering work in the 1960s) has a variety of surprising links to the combinatorics of lambda calculus. In the talk, I will give a brief survey of these enumerative connections, then focus on the 1-to-1 correspondence (originally described in work by Bodini, Gardy, and Jacquot) between linear lambda terms and rooted trivalent maps. The key to understanding this bijection will be combining an interpretation of lambda terms as string diagrams with a Tutte-style decomposition of rooted trivalent maps with boundary. Finally, if time permits, I will discuss a suggestive analogy between typing and edge-coloring, and use this to motivate a deeper study of the surprisingly subtle typing properties of linear lambda terms.