graph - What are the differences between Embedded and Topological in Graph?

Question

In Algorithm Design Manual, page 178 describes some properties of Graph, and one of them is embedded and Topological:

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 significance.

Occasionally, the structure of a graph is completely defined 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. The weights are typically defined by the Euclidean distance between each pair of points.

Grids of points are another example of topology from geometry. Many problems on an n × m grid involve walking between neighboring points, so the edges are implicitly defined from the geometry.

I quite don't understand it:

1. First of all, what exactly does embedded mean here? As long as the vertices have their own geometric positions, then can I call the graph embedded?
2. What does any drawing of a graph is an embedding mean? Does it mean what I said in point 1?
3. What does Topological mean? I don't think it is explained in this description.
4. The examples in this description really confused me a lot. Could someone please use simplest words to let me understand these two terms for graph?
5. Is it really important to get these two term understood?

Thanks

Answer 1

1. I remind you that a graph is just a set of vertices and a set of edges defined on them, so the vertices don't have a geometric position of their own. A drawing of a graph is called an embedding, a drawn graph is called embedded.
2. It means that any way of drawing a graph is called an embedding of that graph.
3. A topological graph is a graph whose vertices and edges are points and arcs, respectively.

Answer 2

Skiena uses geographical friendship graph as an example for embedded graph because each vertex is associated with a geographical point in this world where friends live.

Excerpt from the book - Do my friends live near me? – Social networks are not divorced from geography. Many of your friends are your friends only because they happen to live near you (e.g., neighbors) or used to live near you (e.g., college roommates).

Thus, a full understanding of social networks requires an embedded graph, where each vertex is associated with the point in this world where they live. This geographic information may not be explicitly encoded, but the fact that the graph is inherently embedded in the plane shapes our interpretation of any analysis.

Answer 3

In addition to msj's answer.

Graph = G(V, E), where V is set of vertex and and E is set pair of vertices from V. This is definition of graph as per Skiena. Note how there is no mention of how this graph visually appear (i.e no mention of its topology).

Example (note that it doesn't define where a, b are located in say X,Y coordinate system)

V = { a, b, c, d, e, f } and E = { (a,b), (b,c), (a,e) }

To 'draw' a graph you assign it geometric positions e.g. in X,Y coordinate systems.

|
|           b (2,3)
|   a(1,2)
|
|
|____________________________
 Fig 1

Fig 1 is simply an embedding where we are drawing vertex pairs specified in E

Difference between embedded and topological graph is how does the "topology" comes to be. In any "embedding" you manually assign geometric locations as explained above, but in topological graph you define a "rule" based on which topology of a graph defines itself. e.g. you specify a G(V,E) and define a rule, say "visit each node exactly once" defines the topology which is called "complete graph".