There are a variety of maps available for visitors to Bali, including paper map, plastic maps, guidebooks with maps of the island eyc. The most detailed map of Bali, that is widely available is the Periplus Bali Street Atlas.
The 2005/2006 edition cost 145,000rp in the Periplus shop at Made’s Warung in Seminyak. In Bintang supermarket they charge 195,000rp. Published in Singapore by Tuttlepublishing, the book has 171 pages, with a selection of detailed, clear maps.
Using my GPS to mark small villages on Sunday, I referred to the Street Atlas and was able to utilize their coordinates on the maps to locate them exactly.
Periplus Bali Street Atlas breaks down the island by scaled maps. There are 3 small scale maps giving an overview at 1:200,000, 56 medium maps covering all of Bali including Nusa Penida at 1:60,000-1:75,000 and 45 large scale maps, zeroing in on the population centers, at 1:10,000-1:25,000
Bali is a propinsi (province) of Indonesia. The Periplus Bali Street Atlas breaks down administrative zones into kabupatan (district), kecamatan (municipality), kelurahan (village area) and banjar (village). For example, Jl. Melasti would be in the kabupatan of Badung, the kecamatan of Kuta and the kelurahan of Legian Kaja. The wedding I went to a while back, would be in the kabupatan of Tabanan, the kecamatan of Kediri, the kelurahan of Nyitdah and the banjar of Babakan.
Periplus Bali Street Atlas also give a topographical view of the island, enabling one to see the physical features, which for me, makes life a lot easier, when exploring.