<p>If a vertex is only in one subgraph then its adjacency list will not change. However if a vertex is in both subgraph, then you simply take union of its adjacency list in subgraphs g1 and g2. You don't need to traverse any edge more than twice in case of undirected graph and once in case of directed. </p>

<p>Therefore it takes O(|V| + |E|) time where |V|,|E| are total vertices and edges in graph G</p>

CC BY-SA 4.0
2018-07-05T21:10:39.510Z
2018-07-05T21:10:39.510Z
user2749282
<p>Maybe my solution is just too trivial and therefore wrong, but here is my pseudo-algorithm:<br>
Select any $v \in V_{G1}$<br>
Select any $u \in V_{G2}$<br>
Create a new Edge e with $e=(v,u)$<br>
Done<br>
$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?).  </p>

CC BY-SA 4.0
2018-07-05T01:39:30.457Z
2018-07-05T01:45:23.260Z
2018-07-05T01:45:23.260Z
Panzerkroete
<p>I am looking for an algorithm to construct a graph from two subgraphs. The problem is as following:</p>

<p>Given two graphs g<sub>1</sub>(V, E) and g<sub>2</sub>(V, E), find a graph G(V, E) where V(g<sub>1</sub>) ⊆ V(G), V(g<sub>2</sub>) ⊆ V(G), E(g<sub>1</sub>) ⊆ E(G) and E(g<sub>2</sub>) ⊆ 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(n<sup>2</sup>). Is any better algorithm?</p>

CC BY-SA 4.0
2018-07-13T12:26:00.893Z
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
<graph-theory>
Looking for an algorithm to construct a graph from two subgraphs
James Lu
# Looking for an algorithm to construct a graph from two subgraphs

(Asked by: username_0 on 2018-07-04)

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?

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2018-07-05. Score: 2

If a vertex is only in one subgraph then its adjacency list will not change. However if a vertex is in both subgraph, then you simply take union of its adjacency list in subgraphs g1 and g2. You don't need to traverse any edge more than twice in case of undirected graph and once in case of directed.

Therefore it takes O(|V| + |E|) time where |V|,|E| are total vertices and edges in graph G


---

### Answer by username_3 on 2018-07-05. Score: -1

Maybe my solution is just too trivial and therefore wrong, but here is my pseudo-algorithm:  
Select any $v \in V\_{G1}$  
Select any $u \in V\_{G2}$  
Create a new Edge e with $e=(v,u)$  
Done  
$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?).


---

