This paper describes several optimization techniques used to create an adequate route network graph for autonomous cars as a map reference for driving on German autobahn or similar highway tracks. We have taken the Route Network Definition File Format (RNDF) specified by DARPA and identified multiple flaws of the RNDF for creating digital maps for autonomous vehicles. Thus, we introduce various enhancements to it to form a digital map graph called RNDFGraph, which is well suited to map almost any urban transportation infrastructure. We will also outline and show results of fast optimizations to reduce the graph size. The RNDFGraph has been used for path-planning and trajectory evaluation by the behavior module of our two autonomous cars “Spirit of Berlin” and “MadeInGermany”. We have especially tuned the graph to map structured high speed environments such as autobahns where we have tested autonomously hundreds of kilometers under real traffic conditions.