What is the realization of a graph in $\mathbb{R}^d$?

Question

I am an undergraduate who has been overhearing students talking about realizations of graphs in $\mathbb{R}^d$, and I am curious to know what that means. To be honest, I don't even know what a 'realization' is to begin with. Could someone give an intuitive explanation and possibly an example of a realization of a graph in $\mathbb{R}^1$ and in $\mathbb{R}^2$? I can't seem to find an explanation of these things online! I just hear about them through the grape vine it seems. Thanks!

Answer 1

When a graph is thought of abstractly there are objects called vertices and objects that represent relationships between pairs of vertices that are called edges. So one might have the graph G with vertices a, b, and c and the edges ab, bc, and ca (order of the pairs doesn't matter). Now one can try to represent or realize the graph in some "space" or on some "surface" in a space. So we try to realize G in the Euclidean space of dimension one by picking three points on a line and using parts of the line to represent or realize the edges. One can't do that without edges meeting at points other than vertices. But one could do this for the graph H with vertices a, b, and c and the edges ab and bc - put a at 0, b at 1 and c at 2, so for example the segment 1 to 2 realizes the edge bc (many other choices). However, there is more room in a plane or a sphere sitting in 3-space. So graph G can be realized in a plane or on a sphere in 3-space, using three points in the plane that are not on a line. If one has the graph G* with 5 vertices and every pair of vertices is an edge, the so called complete graph with 5 vertices, then one can't realize that on a plane or the surface of a sphere in 3-space but one can realize it on the surface of a torus (donut) with one hole. It turns out that any graph at all can be realized in 3-space because there is enough "room" so that the edges can be chosen in a way so they meet only at the vertices. It is typically hard to determine the minimum number of holes so that the graph can be drawn on a torus with that number of holes. This is the problem of determining the genus of the graph.