I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double loops for doing this:for all u in G1  for all v in G2    if u.label == v.label then       do something here    end if  end forend forNow the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available? I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism_problem). But here I am not trying to find out if the two graphs are isomorphic. Is there a better/more efficient approach for doing this?
Comparing two graphs
algorithms;graphs;lower bounds
A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.This also assumes that the do something-bit doesn't change the label (and that the order of the do somethings doesn't matter).