Automatic layout sounds like a good job for graphviz, which also does have a CPAN module. By default, it will try to find an optimal layout minimizing the distance based on the given relationship. To make that resemble the geography, you can force the coordinates of the metropolitan center nodes and then connect the branch nodes with invisible edges to their nearest core.
Maybe the complicated object hierarchy you mention actually helps defining the edges?