info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Skiena Algorithms-2e-pg148: Embedded graph
4 views
Skip to first unread message
Veek M
Aug 28, 2015, 5:15:47 AM8/28/15
to
"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?
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?
0 new messages