Analyse the dimension by putting a graph into euclidean space without edge intersection

46 Views Asked by At

Say we have a graph which has maximum $k$-clique as its subgraph. Let us try to put each vertices of the graph into Euclidean space without having any intersection of edges. Note that we assume that each edge is straight line. If my observation is correct, in that case, we need at least $k-1$ dimensional Euclidean space to do that. (like when putting $k-1$ simplex inside Euclidean space.)

In what area of mathematics, this kind of nature is investigated? Or, do you have any good suggestion of keyword to google about this?

1

There are 1 best solutions below

0
On BEST ANSWER

Any graph can be embedded in $\mathbb{R}^3$ with edges represented as straight lines such that no two edges intersect, see e.g. the second answer here. This stems mainly from the fact that straight lines have Lebesgue measure $0$ in $\mathbb{R}^3$, so if you have two edges intersecting, an arbitrarily small perturbation in the position of one of the vertices will remove the intersection.