<p>You might be interested in an <em>online algorithm</em>, which is one that processes the input in a serial manner. Here is a paper with fast algorithms that tests planarity after adding an edge or a vertex, and does so much faster than $O(m+n)$ time (it does so in $O(\log{n})$):</p>

<p><a href="http://epubs.siam.org/doi/abs/10.1137/S0097539794280736?journalCode=smjcat" rel="nofollow">http://epubs.siam.org/doi/abs/10.1137/S0097539794280736?journalCode=smjcat</a></p>

<p>You will be interested in the edge-addition version of this. And you could ask your question with any two edge sets, but since you seem to have info that both $G_1$ and $G_2$ are planar, you can start with the one which is larger, knowing it is planar, then add edges from the other graph one at a time.</p>

<p>In a 'worst case' where $|E_1| = |E_2| = m$, you would have to decide when this $\frac{m}{2}O(\log{n})$ is better or worse than just applying a $O(m+n)$ planarity test.</p>

CC BY-SA 3.0
2016-06-28T23:19:16.157Z
2016-06-28T23:19:16.157Z
JimN
<p>There are a number of ambiguities in your question.  If you are given both $G_1$ and $G_2$ offline, then from a big-$O$ perspective, the problem is $\Theta(n_1+m_1 + n_2+m_2)$. If one or both are given online, then you should follow what Jim said.  It sounds like your measure of efficiency is a practical one, in which case you're better off using industrial software to run the obvious approach.</p>

CC BY-SA 3.0
2016-07-01T01:58:39.830Z
Given the graphs offline, you can always process them an edge at a time. So while $\Theta(n+m_1+m_2)$ holds here, it is the 'obvious one' the question poser already mentioned (Also, the graphs are on identical Vertex sets so $n_1=n_2$) . If we take $m_1 > m_2$, then running the online algorithm after $k$ edges is more efficient when $k$ is $o(\frac{n+m_1}{log{n}})$. Let's not forget that with planar graphs, $m$ is never $\omega(n)$ anyway.
JimN
CC BY-SA 3.0
2016-06-30T23:31:30.393Z
2016-06-30T23:31:30.393Z
Nathan Lindzey
<p>Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs.</p>

<p>Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar? 
That is, an algorithm more efficient than the obvious one of running the standard linear planarity test on the union.</p>

CC BY-SA 3.0
2016-06-12T22:26:21.783Z
Testing planarity for any graph is efficiently solvable. https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Efficient%20Planarity.pdf
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-06-13T11:06:52.377Z
Yea I know, but i wonder maybe the sparse of planar graph may help to improve the algorithm (Efficiently/ Simplicy).
user1387682
CC BY-SA 3.0
2016-06-14T00:23:22.017Z
You can have two planar graphs with embeddings that put the same vertices in the same places, but when you take the union the embedding needs to relocate vertices. This suggests (to me) that you at least wouldn't get a simpler algorithm for testing planarity of the union versus just ordinary planarity testing.
Andrew Morgan
CC BY-SA 3.0
2016-06-14T16:21:42.873Z
What if  I permit  to compute some marks/insights of both planar graph before checking for union? (like mark "suspect nodes" to involve in  K_3,3 , K_5 subgraph and only check them in the union part Or some other property to mark)
user1387682
<graph-theory><graph-algorithms><planar-graphs>
Efficient algorithm for testing planarity of the union of two planar graphs
user1387682
# Efficient algorithm for testing planarity of the union of two planar graphs

(Asked by: username_0 on 2016-06-12)

Let $G\_1 = (V,E\_1)$ and $G\_2 = (V,E\_2)$ both be planar graphs.

Is there an efficient algorithm to check whether the union $G = (V,E\_1\cup E\_2)$ is planar?
That is, an algorithm more efficient than the obvious one of running the standard linear planarity test on the union.

**Tags:** graph-theory, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: Testing planarity for any graph is efficiently solvable. https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Efficient%20Planarity.pdf  
> **username_0**: Yea I know, but i wonder maybe the sparse of planar graph may help to improve the algorithm (Efficiently/ Simplicy).  
> **username_2**: You can have two planar graphs with embeddings that put the same vertices in the same places, but when you take the union the embedding needs to relocate vertices. This suggests (to me) that you at least wouldn't get a simpler algorithm for testing planarity of the union versus just ordinary planarity testing.  
> **username_0**: What if  I permit  to compute some marks/insights of both planar graph before checking for union? (like mark "suspect nodes" to involve in  K_3,3 , K_5 subgraph and only check them in the union part Or some other property to mark)  

---

## 2 answers

### Answer by username_3 on 2016-06-28. Score: 1

You might be interested in an *online algorithm*, which is one that processes the input in a serial manner. Here is a paper with fast algorithms that tests planarity after adding an edge or a vertex, and does so much faster than $O(m+n)$ time (it does so in $O(\log{n})$):

<http://epubs.siam.org/doi/abs/10.1137/S0097539794280736?journalCode=smjcat>

You will be interested in the edge-addition version of this. And you could ask your question with any two edge sets, but since you seem to have info that both $G\_1$ and $G\_2$ are planar, you can start with the one which is larger, knowing it is planar, then add edges from the other graph one at a time.

In a 'worst case' where $|E\_1| = |E\_2| = m$, you would have to decide when this $\frac{m}{2}O(\log{n})$ is better or worse than just applying a $O(m+n)$ planarity test.


---

### Answer by username_4 on 2016-06-30. Score: -3

There are a number of ambiguities in your question. If you are given both $G\_1$ and $G\_2$ offline, then from a big-$O$ perspective, the problem is $\Theta(n\_1+m\_1 + n\_2+m\_2)$. If one or both are given online, then you should follow what Jim said. It sounds like your measure of efficiency is a practical one, in which case you're better off using industrial software to run the obvious approach.

> **Comments:**
> **username_3**: Given the graphs offline, you can always process them an edge at a time. So while $\Theta(n+m_1+m_2)$ holds here, it is the 'obvious one' the question poser already mentioned (Also, the graphs are on identical Vertex sets so $n_1=n_2$) . If we take $m_1 > m_2$, then running the online algorithm after $k$ edges is more efficient when $k$ is $o(\frac{n+m_1}{log{n}})$. Let's not forget that with planar graphs, $m$ is never $\omega(n)$ anyway.  

---

