Re: [boost] [Review] Boost Graphs Library (GGCL)

From: Beman Dawes (beman_at_[hidden])
Date: 2000-08-29 14:11:02

Dietmar Kuehl wrote:

 >> Background: I'm interested in planar graphs because they are the
 >subspecies
 >> of graph used to represent topology when doing digital geography.  See
 >> http://www.census.gov/geo/www/tiger/index.html.
 >>
 >> The topology involved is concerned with 0-cells, 1-cells, and
 >> 2-cells.  These correspond to vertices, edges, and the polygons bounded 

 >by
 >> vertices and edges.  The computer representation is a planar graph.  A 
US
 >> nationwide street map, for example, is a planar graph with over 40
 >million
 >> edges.
 >
 >Interesting... Due to bridges, the German national street map is not a
 >planar
 >graph! It is, however, close to being planar. Depending on your needs, 
the
 >street map might even be a directed graph to cope with one ways.

I would be surprised if internally the German national street map (and 
virtually all high reliability street maps) weren't maintained internally 
as planar.  Otherwise there is no way to check the invariants for 
topological correctness, without which the map is sure to contain 
errors.  They may blow away the vertex representing the bridge crossing for 
the distribution formats, or just mark the vertex as "invisible".  But 
routing and similar algorithms will produce the wrong result if the network 
isn't topologically correct.

--Beman