Lightning will work the same way. Nobody needs to worry about graph theory, they can just generally assume that the graph is fully connected, and that their software will be able to find a path from A to B.
What will be bitcoin's "ISPs"? Who makes sure the graph remains connected and usable? Who invests in the "infrastructure", making sure channels remain well balanced? Some say that Lightning will be self-balancing through a clever set of incentives, but that's again extremely experimental and untested.
Also note the big "net neutrality" thing going on in the US right now. What will prevent big players from teaming up and interconnecting with each other to facilitate transactions while leaving out the rest?
I don't have the answers to any of these questions, maybe it's just FUD. I'm just surprised that bitcoin is a couple of weeks from making such a huge jump into the unknown. It's extremely interesting to be sure, but I feel like some people are going to get severely hurt if this whole thing comes crashing down.
I don't see a reason that exchanges couldn't take on the role of ISP/bank in this situation. Essentially you have an account with 1500 BTC at an exchange, and you say that you want to put 500BTC into a lightning network. Then the bank centralizes itself in the lightning network graph by making connections with other large banks and some major companies.
Of course what we've just done is recreated the modern centralized payment processing scheme on top of the bitcoin network (ie. a mom and pop shop connects to square connects to BoA has my money which doesn't actually exist anywhere, and they make ledger changes and top up later).
You might even be able to make such a system work with no additional transaction fees. But I'm not sure of that.
God I wish this was still true. The internet is so fragmented now I have to have IPs in different nations for a unified experience.