1

Possible Duplicate:
What is the max number of points in R^3, interconnected by generic curves?

Given a set of points connected by edges lying on an euclidean plane, I'd like to find which is the smaller dimension of the euclidean space where the graph can lie without an overlapping of the edges. Is it a standard problem? Which mathematical tools I have to know to manage with this kind of problems? I can obviously guess that I could always take $d=v-1$ where $v$ is the number of verticies but I can't understand which is the smaller dimension.

Thanks

flag

closed as exact duplicate by Greg Kuperberg, Qiaochu Yuan, Scott Morrison♦ Dec 23 2009 at 7:51

2 Answers

5

As Charles points out, you can always embed a graph in three dimensions. The interesting question is how complicated a surface one needs to embed a graph into. The number of handles one has to attach to a spehere in order for a graph to become embeddable is called the genus of the graph, see graph embedding on Wikipedia, which offers other useful information.

link|flag
+1 for suggesting related question with interesting results – Aaron Mazel-Gee Dec 23 2009 at 7:17
Actually I was interested in: given a random graph, I'd like to know if this can be seen as the tessellation of a Manifold and which is its dimension, or something like this. I'm not really able to write the right question, but mine was not what I wanted to know. I guess that is something related to the genus. Could you give me some references? My ideas in this field are really fuzzy – random3f Dec 25 2009 at 18:36
I am not an expert in this topic, but a quick Google search suggests people.math.gatech.edu/~thomas/PAP/genus.pdf Perhaps you can have a look at this and ask another, more informed question on mathoverflow to get the experts' attention. – Andrej Bauer Dec 26 2009 at 0:50
6

Any graph embeds into $\mathbb{R}^3$. See Wikipedia.

link|flag
4 
 Or the previous question on this subject: mathoverflow.net/questions/9293/… – Qiaochu Yuan Dec 23 2009 at 3:14
Ahh, missed that question. Anyways, what Qiaochu said. – Charles Siegel Dec 23 2009 at 3:20
...assuming the cardinality of the vertex set is at most continuum. – S. Carnahan♦ Dec 23 2009 at 7:01
True, though in context, random3f started out with a "Given a set of points connected by edges lying on an euclidean plane" which means it must be continuum or smaller. – Charles Siegel Dec 23 2009 at 7:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.