Efficient algorithm for testing planarity of the union of two planar graphs 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.
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.