Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.games.development.programming.algorithms > #107

Skiena Algorithms-2e-pg148: Embedded graph

Show all headers | View raw

"Embedded vs. Topological ? A graph is embedded if the vertices and edges 
are assigned geometric positions. Thus, any drawing of a graph is an 
embedding, which may or may not have algorithmic signi?cance."

What's that stuff about a drawing being an embedding? Drawings don't have a 
coordinate system - an axis pair etc

"Occasionally, the structure of a graph is completely de?ned by the geometry
of its embedding. For example, if we are given a collection of points in the
plane, and seek the minimum cost tour visiting all of them (i.e., the 
traveling salesman problem), the underlying topology is the complete graph 
connecting each pair of vertices."

Whaat? "completely defined by the geometry of its embedding"??
A topology is unaffected by a change in shape and size so..
is he saying that the graph (with edges, weights and vertices connecting the 
various locations) is a topological graph - the lay of the land (has all the 
info required to solve the problem).

Basically an embedded graph requires a coordinate system and a topological 
graph is self contained because weights are used to compute cost and the 
interconnections are described by the edges. Is this what he's trying to 
say?

Back to comp.games.development.programming.algorithms | Previous | Next | Find similar

Thread

Skiena Algorithms-2e-pg148: Embedded graph Veek M <vek.m1234@gmail.com> - 2015-08-28 14:45 +0530

csiph-web