I assume you mean the larger backbone links that link the world together?
Then this link will definately help:
http://www.geog.ucl.ac.uk/casa/marti.../isp_maps.html
How about a C&W view:
http://www.cw.com/our_network/network_maps/
AFAIK many telco's install the links and then either share the cost (of install) or rent them out to other telco's
With regards 2nd Q - Right answer is probably both, but I would guess majority come under the sea!
HTH?