We first give a high-level idea of the algorithm referring to lines of the pseudo code given below. We “force” the routes of any two agents to form a tunnel for every possible combination of starting nodes and labels of the two agents. By Proposition 2.1, this suffices to guarantee rendezvous. Any starting configuration of robot i placed at node v and robot j placed at node w by the adversary corresponds to a quadruple ( i, j, s $^{′}$, s$^{′′}$) where s ′ is a sequence of ports inducing a path from v to w and s ′′ is a sequence of ports inducing the reverse path from w to v . Each agent constructs its route in phases. At the beginning and at the end of each phase the agent is in its starting node. At phase k the previously constructed initial part of the route r$_{hist}$ is extended while the agent processes quadruple ϕ$_{k}$ (some of the extensions are null). This extension guarantees that the routes of agents of the corresponding starting configuration will form a tunnel. When agent with label l processes quadruple ϕ$_{k}$ = ( i, j, s $^{′}$, s$^{′′}$) nothing happens if l = i and l = j (line 4). If l = i , agent i tries to extend its route to guarantee rendezvous with agent j under the hypothesis that a path from v to w corresponds to the sequence s ′ of ports and the reverse path corresponds to the sequence s $^{′′}$. For this to happen, the agent first tries to follow the path r ( s $^{′}$) induced by the sequence s ′ of ports (lines 8-11). This attempt is considered successful if the following conditions are satisfied: • at consecutive nodes of the traversed path, ports with numbers from the sequence s ′ are available, • the reverse path corresponds to the sequence s ′′ of ports. When the attempt is successful (the condition of line 13 is satisfied) the agent is at node w and it simulates the first k − 1 phases of the execution of the algorithm by agent with label j starting from w . The effect of this simulation is the path r$_{sim}$ . Upon completion of this part, agent with label i returns to w . Now the agent is able to further extend its path to form a tunnel with the route of agent j (line 16). Finally, whether the attempt to follow the path r ( s $^{′}$) is successful or not, the agent with label i backtracks to v (line 17). If l = j , the above actions are performed with the roles of i and j reversed and the role of s ′ and s ′′ reversed. Algorithm GraphRV calls the recursive function GraphRVREC . This function is called in two different modes controlled by the boolean mode . In the “main” mode ( mode = true ) the function is executed indef- initely, until rendezvous. In the “simulation” mode ( mode = false ), the function is executed for all values up to a given p , or until rendezvous, whichever comes first. The symbol ⌢ denotes the concatenation of se- Theorem 3.1. Algorithm GraphRV guarantees asyn- chronous rendezvous for arbitrary two agents starting from any nodes of an arbitrary connected graph. Figure 1: Tunnel between the routes of two agents quences. INPUT: A starting node v ∈ V and a label l of the agent. OUTPUT: A rendezvous route r . GraphRVREC ( v, l, 0 , true ); GraphRVREC (node v, label l, integer p, boolean mode ) 1 k := 1; r := λ ; 2 while not rendezvous and ( k ≤ p or mode ) do 3 let ϕ$_{k}$ = ( i, j, s $^{′}$, s$^{′′}$); r$_{hist}$ := r ; 4 if l = i or l = j then 5 if l = i then s 1 := s $^{′}$; s 2 := s $^{′′}$; l ′ := j ; 6 else s 1 := s $^{′′}$; s 2 := s $^{′}$; l ′ := i ; 7 let s 1 = ( p 1 , . . . , p$_{n}$ ); m := 1; r ( s 1 ) := λ ; 8 while m ≤ n and p$_{m}$ is a port do 9 r ( s 1 ):= r ( s 1 ) ⌢ ( e$_{m}$ ) where e$_{m}$ corresponds to port p$_{m}$ ; 10 let a$_{m}$ be the port corresponding to e$_{m}$ at its other endpoint; 11 m := m + 1; 12 r := r ⌢ r ( s 1 ); 13 if s 2 = ( a$_{n}$, . . . , a 1 ) then 14 let w be the current node; 15 r$_{sim}$ := GraphRVREC ( w, l $^{′}$, k − 1 , false ); 16 r := r ⌢ r$_{sim}$ ⌢ r ( s 1 ) ⌢ r$_{hist}$ ⌢ r ( s 1 ) ⌢ r$_{sim}$ ; 17 r := r ⌢ r ( s 1 ); 18 k = k + 1; 19 return r Algorithm GraphRV function route of agent i : route of agent j : tunnel: r v ⌢ q ⌢ r w ⌢ q ⌢ r v ⌢ q ⌢ r w ⌢ q$_{· · ·}$ r w ⌢ q ⌢ r v ⌢ q ⌢ r w ⌢ q ⌢ r v ⌢ q . . . r v q r w q r v q r v r v r w q w