If the cities are static why do you have to pass x, y coordinates in as parameters? If they are static why are their coordinates not just saved statically with the city? Cities do not change location! ( Well, not that often...
)
Another thing, I would not use the Java 2D API for this. Personally, I love the 2D API, but for applets it is better to stick with just AWT if you can, because anything added after Java 1.1 requires the user to download the Java 2 Plugin. From what you describe, this program would be no problem with using only AWT functionality.
HTH,
-Nate