0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Testing planarity for any graph is efficiently solvable. cs.princeton.edu/courses/archive/fall05/cos528/handouts/… $\endgroup$ – Mohammad Al-Turkistany Jun 12 '16 at 22:26
  • $\begingroup$ Yea I know, but i wonder maybe the sparse of planar graph may help to improve the algorithm (Efficiently/ Simplicy). $\endgroup$ – user1387682 Jun 13 '16 at 11:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Andrew Morgan Jun 14 '16 at 0:23
  • $\begingroup$ 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) $\endgroup$ – user1387682 Jun 14 '16 at 16:21
1
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JimN Jul 1 '16 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.