If you can't find a map, you can always just rip one off of Wikipedia and custom edit it. Paint is OK, but I recommend a program called SketchBook, as it, in my opinion, a bit more customizable and usable.

As to the background of the world, here's a suggestion.

A list of many of the various different ways that empires can get split up, assuming one empire changed into multiple entities, along with a historical example if possible:

EXTERNAL MEANS
Spoiler
Show

1. Invasion.
1.a. Invasion with rebels. Rebel parties can be unified or split up, according to any other means on this list. (Do I even need an example here?)
1.b. Invasion foothold. The invasion is not complete. (British invasion of France, 100 Year's War)
1.c. Invasion with issues. The invading army is split into multiple groups for any number of reasons (Spanish/Mercenary armies invading the Netherlands. Reason of issue: pay for the troops)
1.d. Invasion by dissent. Invading country uses spies to pit the country against itself and spur inner rebellion and dissent using the Internal Means list. (Jacobite wars. The Jacobites (English/Scottish Dissenters) were funded by the French to fight the English)
2. Pact/Diplomacy
2.a. War Lost Divide. The losing country of a war is forced to divide itself into various parts. (Germany post WWII, East and West)
2.b. UN Peer Pressure. A group of allies tell you to give them land. (Not sure this has happened, but I'm not omniscient)
2.c. "Too Much for One Man." Voluntary agreement to share/divide power with an ally. Could mix with certain Internal Means elements.
2.d. Sale. Buying some other country's land from 'em. (Louisiana Purchase)
3. Other. I'm sure there are some more, and I'll update the list if need be.


INTERNAL MEANS
Spoiler
Show

1. Inheritance
1.a. "Don't Divide the Kingdom!" A king divides his land up between his children and/or generals (Alexander the Great divided his land three ways between his generals.
1.b. Backstabber. A sib creates his own kingdom-breakaway. (Example: Practically. Every. Reign. Of. France.)
2. Intrigue
2.a. Political enemies. (Our very own Hinjo V Kubota)
2.b. Political split. Secession, more or less (The obvious American Civil War)
2.c. Rebellion (general or specific, concentrated or wide-spread. Your people hate you, and they fight you. (French Revolution)
3. Other.


Those should spark your mind a bit, I hope. :D.

As to names, which ones have names, and which need 'em? I'd love to help with that, if you need it.