Graphs, links, and duality on surfaces