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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Testing planarity for any graph is efficiently solvable. cs.princeton.edu/courses/archive/fall05/cos528/handouts/… $\endgroup$
    – Mohammad Al-Turkistany
    Commented Jun 12, 2016 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
    Commented Jun 13, 2016 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
    Commented Jun 14, 2016 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
    Commented Jun 14, 2016 at 16:21

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 1, 2016 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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