Self-driving vehicles rely on detailed semantic maps of the environment for operating. In this letter, we propose a method to autonomously generate such a semantic map enriched with knowledge of parking spot locations. Our method detects and uses parked vehicles in the surroundings to estimate parking lot topology and infer vacant parking spots via a graph-based approach. We show that our method works for parking lot structures in different environments, such as structured parking lots, unstructured/unmarked parking lots, and typical suburban environments. Using the proposed graph-based approach to infer the parking lot structure, we can extend the estimated parking spots by 57%, averaged over six different areas with ten trials each. We also show that the accuracy of our algorithm increases when combining multiple trials over multiple days. With ten trials combined, we managed to estimate the whole parking lot structure and detected all parking spots in four out of the six evaluated areas.