Comments on Is there a way to encode a unique arrangement of vertices of a graph with a unique short word?
Parent
Is there a way to encode a unique arrangement of vertices of a graph with a unique short word?
I call graphs $G_1$ and $G_2$ distinct iff (i) $G_1$ has a different arrangement1 of vertices than $G_2$ and (ii) $G_1$ and $G_2$ have the same number of vertices. All other properties of $G_1$ and $G_2$ have no effect on distinguishing them. For example, $G_1$ and $G_2$ may be the same even if the number of edges of the two graphs is different.
Example:
| $G_1$ | $G_2$ | $G_3$ |
|---|---|---|
 |
 |
 |
Here, $G_1 = G_2$ but $G_1 \neq G_3 \iff G_2 \neq G_3$.
I'm wondering if there is a way to create a unique correspondence between a graph and a single word (any string of letters, possibly gibberish) of the English alphabet. That is to say, distinct graphs $G_1$ and $G_2$ must necessarily map to a different word. It is preferable that the word has 4-7 characters. Additionally, the word may contain a single integer from 1-9 at the end of it. Hence, for example, $G_1$ could map to the word GLBXR7 and $G_2$ could map to the word MMTR.
I'm looking for an algorithm to map every distinct graph with a unique word. You may assume that every graph has the same number of vertices.
A very crude attempt is to label each vertex of a graph with letters from left to right, top to bottom and concatenate them in that order. However, I don’t think this is sufficient for uniqueness.
Clarifications
I attempt to clarify some of the potentially ambiguous elements of my post.
-
I agree that the notion of a "graph" is not entirely relevant here. I actually chose it because I am working with this sort of information in another project where connectivity matters. Nonetheless, viewing this as a point cloud is perfectly fine; you may edit the tag(s) if you'd like.
-
There doesn’t need to be a bijection between words and graphs. Every unique graph should map to a unique word, but every word need not map to a graph.
-
Since I placed a finite restriction on the length of a word (4 - 7 characters), I attempt to set an upper bound on the number of vertices of a graph.
$$\text{Number of words} = \sum_{k = 4}^7 \left(26^{k-1}\cdot (26 + 9)\right) = 11244509640$$ $$\text{Number of graphs with} \le n \; \text{vertices} = \sum_{k = 1}^n \sum_{i = 1}^k {{k - 1} \choose {i - 1}} = 2^n - 1$$ $$11244509640 = 2^n - 1 \implies \lfloor n\rfloor = 33$$
- I apologise for not making this point before, but the algorithm should be human computable, that is, possibly something a human can do in their head in about 15 seconds.
1I'm not sure how to perfectly formalise the notion of an arrangement, but a possible necessary and sufficient condition is to consider the number of vertices to the left, right and along the same vertical axis as each vertex of graphs $G_1$ and $G_2$—if any of the values are different, the graphs are distinct.
Post
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| Carefree Explorer | (no comment) | Aug 21, 2022 at 08:53 |
I'm going to assume your points are lying on an integer grid. I'm also assuming you always have a finite number of points.
Then one way to make words for your point clouds is to enumerate the grid points, for example by starting at the origin and going in a spiral. Then you can assign an unique finite bit-string to each configuration by starting at the origin, following the spiral and note a $0$ for any unoccupied grid point, and a $1$ for any occupied grid point, terminating as soon as you've covered all points (that is, all occupied grid points). Note that the last obtained digit that way is always a $1$.
Now reverse that bit string. This ensures the first it is always $1$ (except for the empty cloud, which gets a single $0$), and therefore you can interpret the bit string as binary representation of a natural number, thus getting a bijection between point configurations and natural numbers.
Now all that remains is to map natural numbers to words. That's a pretty standard problem, and the best way to do so depends on the typical properties of your point arrangements. For example, if your points are generally always close to the origin, then you may just convert the number to base 26, and write it down using the 26 letters of the alphabet as digits. OTOH that may be a bad strategy if your points are frequently far from the origin.
Let's look at an example:
Here we see a graph with four points at the coordinates $(0,\pm 1)$, and $(\pm 1, 0)$. Starting at the origin (beginning of the spiral), we get the bit string $01010101$. Note that after the fourth $1$, we've covered all the dots, therefore we stop.
Reversing the bit string then gives $10101010$, which corresponds to the number $90$. Using the base-26 strategy with a=0, b=1, …, z=25, the resulting word is dm.
1 comment thread