Abstract: There is a beautiful theory of polytopes associated to bipartite plane graphs, due to Alexander Postnikov, Tamas Kalman, and others. Via a construction known as the median construction, this theory extends to knots and links -- more specifically, minimal genus Seifert surfaces for special alternating links. The complements of these Seifert surfaces also have interesting geometry. The relationships between these objects provide many interesting connections between graphs, spanning trees, polytopes, knot and link polynomials, and even Floer homology. In recent work with Kalman we showed how these connections extend to contact geometry. I'll try to explain something of these ideas.