I am looking for an algorithm to construct a graph from two subgraphs. The problem is as following:
Given two graphs g1(V, E) and g2(V, E), find a graph G(V, E) where V(g1) ⊆ V(G), V(g2) ⊆ V(G), E(g1) ⊆ E(G) and E(g2) ⊆ E(G). I use adjacency list to store data and merge two graphs by visiting vertex/edge. However, the time complexity is higher than O(n2). Is any better algorithm?