Search code examples
algorithmdata-structuresgraphtopology

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


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


Solution

    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.