1

When adding nodes to a graph with a restriction that all nodes in the graph have a direct connection to all other nodes, how can one detect when a higher dimension is needed so the edges do not cross each other? By crossing I mean one can stretch an edge, circle around all other nodes and not touching any other edge.

For example, three nodes form a triangle and can reside in a 2D plane. Adding one node you can still put four nodes in a 2D plane without crossing edges. But adding the fifth node you have to go to 3D to avoid edge crossing.

It seems like any time a prime number of nodes is added the dimension needs to bump up.

Mike Pierce
  • 18,938
lsha
  • 11
  • 1
    What do you mean by "and so on"? What graph can't be drawn in three dimensions without edge crossings? – bof Sep 14 '16 at 23:16
  • 1
    As per @bof, here is a reference explaining why all graphs can be embedded in 3-space: http://link.springer.com/chapter/10.1007%2F3-540-58950-3_351 and https://en.wikipedia.org/wiki/Graph_embedding – Mosquite Sep 14 '16 at 23:30
  • Maybe crossing is not the right word to use, in 3-space if all N nodes are connected to every other node, and if I stretch one of the edge and try to encircle the other N-2 nodes is it guaranteed there is a path that does not intersect all other edges? – lsha Sep 15 '16 at 01:00
  • "*... stretch one of the edge and try to encircle the other N-2 nodes ..." It is not clear what you are describing here. – Mike Pierce Sep 15 '16 at 01:36

1 Answers1

2

When you say "all nodes have a direct connection to all other nodes", it sounds like you are describing a complete graph.

A graph can be embedded in a one-dimensional space if and only if the graph has no cycles and no vertices of degree higher than two. So the largest complete graph we can embed in one dimension has two vertices.

There are a few criterion used for if a graph can be embedded in two-dimensional space. We call such a graph planar. One of the more well-known criterion is Wagner's Theorem, which states: "A graph is planar if and only if it does not contain either the complete graph on five vertices or the complete bipartite graph on three and three vertices as a minor." So by this theorem, the largest complete graph we can embed in two dimensions has four vertices.

Beyond two dimensions, every complete graph can be embedded in three-dimensional space. To outline an inductive proof of this, note first that a graph with a fewer than four vertices can be embedded in three dimensions without crossing edges. For the inductive step, suppose that for some $n>3$ we can embed any graph with $n$ vertices in three dimensions. Then given a graph with $n+1$ vertices, using our induction hypothesis we can find an embedding of the subgraph containing all but one vertex $v$ into our three dimensional space without crossing edges. Now consider the collection of all the planes such that each plane contains exactly three vertices of the embedded subgraph. There exists a point in your space that is not contained in any of these planes. Placing vertex $v$ at this point will induce an embedding of the graph such that no edges cross.

Mike Pierce
  • 18,938