With that map, I was able to get the title for repede. As you might notice, it's not 100% filled in. I'd say that's 99% filled in.
1. Go over the entire continent you start on. When I first got the access to the dog map, that entire area was already filled in blue (except for the area around Nor Port). I hadn't used any mats or other tent-like items until I was near the end of the first act of the game. (it also confused me as to why you would use mats on the overworld, since I had never had but some areas were blue. I just assumed i must have had used a mat and forgotten).
2. Some areas are so small, that when you turn on the dog map to view your process - it'll appear covered. Use the field selection while looking at the world map. (LT/RT). Focus on the tiny bits of area you can barely see.
3. For the Truffdae Mountains, there is a tiny piece of land jutting out just above them, land there. Go as far south as possible and check your menu to make sure the area says the mountains, then use a mat. Otherwise, the only time you can land in that area is after defeating the final boss.
4. To be able to land on snowy areas, you need to participate in the dragon races up to level 3. In order to do this, approach mt. temza during any part of the third act of the game. There will be an automatic scene. Then, after visiting the blade drifts of zophier.. find myorzo. Go into town and find the boy down the steps to the southeast. You can use the overmap (press x) to see the locations of the rings. (Note to people with SD TVs: I had a hard time seeing the rings on the map. I had to really adjust my color settings in order to see them. You might have to do the same)
5. After the final dungeon has appeared.. many places will change. A lot of places you couldn't land on before (because of water or mountians,) will be available. This is the earliest you can mark these places. So in other words: you cannot finish the dog map until the very end of the game.
6. I forget the exact details of the progression of the quest but there are four events that happen during it. About 50% of the way through, there will be a scene. At this point you have to talk to a dog in Zaphias, and a cat in dahngest (the cat will be on the bridge, not to the left in an area you can't reach). Then, once you're about 90% through and you have access to Aurnion, go to the watch tower to the far west in town. There will be a scene with the rival dog. At this point it's believed the dog will stop trying to mark his territory. After your map looks like the one above, go back to Zaphias in the lower quarter. Outside the Inn/Tavern/Yuri's room is a save point. The dog you get the title from (and finish the quest), will be standing to the left of it. If the dogs not there, you haven't met all the requirements yet.
7. Use mats. They're the cheapest.
8. Because you have to fight in order to use another mat, it's also a great time to practice cooking. The Hot Springs/Spa has all 34 cooking ingredients (unsure if it does all the time). This area is located on the northwestern continent . Hidden in a forest of trees. Look for odd circle lines in the forest.
Feel free to add, in case I've forgotten something! (sorry for any spelling errors!)
Even us girls play games too, and some of us even visit GameFAQs! ;)
All i did was flying with Ba'ul and press Y to bring up the menu. Then, i look at the top right to see the location, use a mat and fly with ba'ul again until the name of the location change then use a mat again and so on. You dont have to sleep on a small island if the name of the location is the same as the one on a bigger island. It will mark automatically.
They keys to get 100% s Ba'ul and the location displayed at the top right of the menu.