I'm unfamiliar with graph theory but was wondering if this has been thought about
An idea that occurred to me yesterday relates to the "*planar dimensionality of a graph*" which means the minimal number of dimensions necessary in which to project the graph such that no edges intersect with eachother. For example, the intrinsic dimensionality of a planar graph is $2$. A graph for which intersections only exist between one single node $n_i$ and any number of other nodes $n_j, j\ne i$, embedding this graph in 3 dimensional will remove any line intersections simply by the definition of a line emanating from a point (because the only place the line segments representing edges intersect is at the node itself and therefore they intersect nowhere else).
Once you can find the dimensionality of a graph as well as an appropriate embedding of the graph in those dimensions (using someforce based spring layout model) then things get interesting.
If the graph has intrinsic dimensionality $n$, by projecting the graph into dimensions $n+1$ and force laying out the graph in these dimensions you obtain a continuous space curve. The position of a node along dimension $n+1$ converges such that the euclidean distance between any two nodes in this $n+1$ space is exactly equal to their edges distance.
*Now we have found the most perfect intrinsic spatial embedding of a graph* because the distance between all the nodes in this space is exactly equal to the weight of their edges *AND* the space approximation created by the graph lattice is continuous.
We can start playing with the physics of this high dimensional graph manifold, for example, by fitting a field function to it in the context of neuroscience.
Has this been thought about before?
All finite graphs can be embedded in three dimensions. Assign the vertices random points in [0,1]3 subset of R3, and use straight lines joining them. The probability of two edges touching is zero. Therefore there are infinitely many embeddings of a given finite graph in R3.
Hi Professor Stewart
Thank you so much for your answer. At this point all I can do is computational data analysis without being able to prove these graph theorems myself. I have two follow up questions which I would really appreciate if you answer.
Is there guaranteed to be a projection of the graph onto R3 such that the distance between all the nodes is equal to the weight of their edges?
If the answer to the previous question is yes, will all the points on the graph in this projection (for which the distance between points/nodes is equal to their edge weight) necessarily live on a continuous surface?
Akiva
See,
Onuttom Narayan, Iraj Saniee, Large-scale curvature of networks
Physical Review E (statistical physics), Vol. 84, No. 066108, Dec. 2011.
The key observation is that whereas any finite graphs embed in R^3 as said, there are graph families, eg grid graphs, that embed only in R^d for each integer (and fractional!) d >0. Eg the family of Euclidean hyper cubic grids in R^4 embed in R^4 and not R^3. In addition, there are graph families that don't embed in any R^d, for any finite d, eg infinite regular trees (with degree >2) which are special cases of hyperbolic grids. These naturally embed in hyperbolic spaces whose volume expands much more rapidly than r^d for a 'sphere' radius r -- this means Euclidean spaces are too tight for them. Hence the need for hyperbolic spaces. Hyperbolic spaces themselves come with local dimension d, for every integer (or rational) d >0. The PRE paper cited above discusses these and more.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics