# Looking for an algorithm to construct a graph from two subgraphs

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?

• In the absence of any other conditions on $G$, you seem to be asking about how to find the union of two sets (once for the vertices, and once for the edges), which can be done in $O(\alpha(n))$ time, where $\alpha(x)$ is the inverse Ackermann function. – András Salamon Jul 13 '18 at 12:26

Select any $v \in V_{G1}$
Select any $u \in V_{G2}$
Create a new Edge e with $e=(v,u)$
$G=(V,E)$ would be $(V(G1) \cup V(G2),E(G1) \cup E(G2) \cup e)$then. As far as I see this algorithm would fit into that what you want and you can guess the complexity (what actually should be n in your question?).