Easier question: Let's say you have a single node in this graph of ${10}^{100}$ nodes.  You want to figure out where that single node should be embedded in your 100-dimensional space, but you only care about its embedding location relative to a few specific other nodes.

You have the following affordances:

1. List the edges that originate at a node. The edges will always be returned in the same order for the same node, but the order is not necessarily the same for different nodes (i.e. the first edge may point along the 57th axis for one node and in the 22nd axis for a different node)
2. Given an edge, retrieve the node at the far end of that edge
3. Compare two nodes to see if they are the same node as each other

That is to say, if you have the following problem definition

import random

class Node:
    key = None
    edges = None

    def __init__(self):
        self.edges = []

class Edge:
    _src = None
    _get_dst = None
    _dst = None

    def __init__(self, src, get_dst):
        self._src = src
        self._get_dst = get_dst

    def get_dst(self):
        if self._dst is None:
            self._dst = self._get_dst()
        return self._dst

class Graph:
    def __init__(self, axis_length, n_dims):
        self.axis_length = axis_length
        self.n_dims = n_dims
        self._nodes = {}
        self._next_node_id = 1

    def get_node_at(self, coords):
        axis_order = list(range(self.n_dims))
        random.shuffle(axis_order)
        if coords not in self._nodes:
            node = Node()
            node.key = self._next_node_id
            self._next_node_id += 1
            for axis in axis_order:
                if coords[axis] == 0:
                    continue
                dst_coords = list(coords)
                dst_coords[axis] -= 1
                dst_coords = tuple(dst_coords)
                def make_edge(dst_coords):
                    def get_dst():
                        return self.get_node_at(list(coords))
                    return Edge(node, lambda: self.get_node_at(dst_coords))
                edge = make_edge(dst_coords)
                node.edges.append(edge)
            self._nodes[coords] = node
        return self._nodes[coords]

    def get_random_node(self):
        return self.get_node_at(tuple([random.randint(0, self.axis_length-1) for _ in range(self.n_dims)]))

and you want a function which will take an arbitrary node and give you the coordinates of that node in a consistent basis in finite time with arbitrarily high probability of correctness

class ComputedBasis:
	def __init__(self):
		self.node_positions_by_key = {}

	def get_coords(node):
    	# Given a node, give the coordinates of that node in some
    	# consistent basis 
    	pass

I claim that this is indeed possible to do, and the steps to do it look nothing like "compute ${10}^{100}$ things".

Edit: To be explicit about the motivation, once we define this function, we can find a path from our position to the sandwich using something like

def path_to_sandwich(my_node, sandwich_node):
    basis = ComputedBasis()
    my_coords = basis.get_coords(my_node)
    sandwich_coords = basis.get_coords(sandwich_node)
    for axis, (my_pos, sandwich_pos) in zip(my_coords, sandwich_coords):
        if my_pos < sandwich_pos:
           raise(f"""
               Can't get to sandwich from here!
               I can only travel towards the origin on each axis.
                   axis: {axis}
                   my_pos: {my_pos}
                   sandwich_pos: {sandwich_pos}
           """)
     return get_path(basis, my_node, sandwich_node)

def get_path(basis, start_node, goal_node):
    curr_node = start_node
    path = [curr_node]
    goal_coords = basis.get_coords(goal_node)
    while curr_node != goal_node:
        curr_coords = basis.get_coords(curr_node)
    	# Find the first axis where we need to move towards the goal along that axis.
    	for axis, (curr_pos, goal_pos) in zip(cur_coords, goal_coords):
    	    if curr_pos > goal_pos:
    	         step_coords = [p for p in curr_pos]
    	      	 step_coords[axis] -= 1
    	      	 step_coords = tuple(step_coords)
    	      	 break
    	for edge in curr_node.edges:
    	    dst_node = edge.get_dst()
    	    dst_coords = basis.get_coords(dst_node)
    	    if dst_coords == step_coords:
    	    	step_node = dst_node
    	    	break
    	curr = step_node
    	path.append(curr)
    return path

Note that my framing of the problem is slightly different, in that (0, 0, 0, ..., 0, 0, 0) is the point from which there are no outbound edges, rather than (10, 10, 10, ..., 10, 10, 10) in your version. Doesn't really make a difference logically, just makes the code more readable.

the maximum plan length is only $10\cdot 100=1000$ steps

You mean the maximum length for an efficient/minimal plan, right? Maybe good to clarify (even if obvious in this case). Just a thought.