Definition/Clarification of Graph Embeddings

Question

Recently I started reading about graph embeddings, but I am unable to grasp its definition from Wikipedia. Can anyone explain this term with an example.

Answer 1

A graph is just an abstract idea, whereas a graph embedding is an actual physical instance of a graph that has to be drawn (or embedded) onto some surface.

---

In order to understand what a graph embedding is, it helps to first define what a graph is.

Definition: A graph is a set vertices and a set of edges connecting those vertices. In a way we can think of a graph as a set of pairs of values, where each pair is an edge and each value is a vertex. To give an abstract example consider the graph $G = \{\{1,a\},\{\text{blue},a\},\{1,\text{blue}\}\}$.

Note that this definition doesn't at all mention a drawing or a picture of the graph; it's just a list of pairs. A graph embedding is where we have to take a graph and actually draw a picture of it on some surface. For example, consider these three drawings of $K_4$ in $\mathbb{R}^2$ (a flat surface):

Typically we require that no edges cross in a drawing of a graph to call it an embedding. This because we want to be consistent with the topological definition of an embedding. So really only the second and third drawings of $K_4$ above are embeddings into $\mathbb{R}^2$. Because we can embed $K_4$ in the plane, we say it is a planar graph. And of course you can start talking about embedding graphs on other surfaces. For example here is a graph embedded on a torus:

_{Image originally from www.ics.uci.edu/~eppstein/0xDE/F24/3dtorus.png}

And then an obvious question arises:

Question: Given a surface, what graphs can be embedded on that surface?

We've seen above that $K_4$ can be embedded on the plane, but it turns out that $K_5$ cannot! In fact we have a complete characterization of all graphs that can and cannot be embedded on the plane. The question of which graphs can and cannot be embedded on a torus, though, is still unanswered.

Answer 2

I think the best example to understand the nuanced difference between Topological vs Embedded Graphs is the example Steven Skiena gave in his book.

If we assumed a social graph where Vertices are people and Edges are the connections between them, we can assume a friendship relation between two people would be modeled as an undirected edge between two people/points.

and if we asked the question "Do my friends live near me?", we would find that most of our friends live near us or has lived near us (old college roommates). One could argue that they are only friends because they live/have lived near us. This geographic info strongly influences our understanding of the Social Graph, and it may not be explicitly encoded, but the fact that the graph is inherently embedded in the plane shapes our interpretation of any analysis.

such info would not be possible from a topological Graph for example.