As diagrams? I couldn't find anything, who used them then?

Yes. If Knuth wasn't making stuff up then you can find some historic accounts (1300s-1500s) in "Two Thousand Years of Combinatorics."

More recently, Euler's paper in 1736 didn't have what you'd recognize as a modern graph diagram, Konig's textbook in 1936 did, and the papers developing the subject between those dates eventually used the modern notion of lines connecting dots as a way to represent edges and nodes.

Yes, your second paragraph was basically what I thought was the case, it does seem quite recent. I don't have access to the Knuth article, I'd love to know what he means. Ramon Llull maybe?

The "Packet Boat and Steamship Connections between Europe and Overseas Ports" is a network diagram: https://exhibits.stanford.edu/dataviz/feature/exploring-time

The closest thing commonly seen in modern visualisation is the "Radial Tidy Tree": https://observablehq.com/@d3/radial-tidy-tree