Boost logo

Boost :

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
>> of graph used to represent topology when doing digital geography. See
>> The topology involved is concerned with 0-cells, 1-cells, and
>> 2-cells. These correspond to vertices, edges, and the polygons bounded

>> vertices and edges. The computer representation is a planar graph. A
>> nationwide street map, for example, is a planar graph with over 40
>> edges.
>Interesting... Due to bridges, the German national street map is not a
>graph! It is, however, close to being planar. Depending on your needs,
>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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at