2
$\begingroup$

I want a hueristic algorithm for the following problem. Here, $V(G)$, $E(G)$ respectively refer to the vertex set and edge set of a graph $G$.

Input: two planar bipartite graphs, $G,H$ and a map $\phi: A\to V(H)$, where $A$ is a subset of $V(G)$.

Task: determine if there is a (bijective) map $\phi': V(G) \to V(H)$, such that $(\phi(x),\phi(y)) \in E(H) \iff (x,y) \in E(G)$, and the restriction $\phi'\mid_A$ is $\phi$. (i.e. $\phi'(a) = \phi(a)$ for all $a \in A$)

Does there exist a practical fast running algorithm for determining if such a $\phi'$ exists? If not, does there exist a simple heuristic algorithm which has a "decent chance" of answering in the affirmative.

I'm looking for an algorithm I can actually understand and code myself, rather than use a large complicated system like nauty.

$\endgroup$
  • 2
    $\begingroup$ The paper "Algorithm and Experiments in Testing Planar Graphs for Isomorphism" by Kukluk et al. presents an implementation of an $O(n^2)$ time algorithm for planar graph isomorphism. Have you taken a look at it? $\endgroup$ – Laakeri Feb 3 at 19:02
  • 1
    $\begingroup$ I think bipartiteness doesn't actually buy you anything: You can turn any two graphs into bipartite graphs by subdividing (adding a vertex "halfway along") each edge, and the resulting graphs will be isomorphic if the original two were. To prove the other direction ("the original graphs are isomorphic if the subdivided ones are"), I think it suffices to subdivide and then add 3 leaves to every original vertex: the subdivision vertices are now the only ones with degree 2, so they can't produce false positives by being confused with original vertices. $\endgroup$ – j_random_hacker Feb 3 at 20:04
  • $\begingroup$ Though if the graph has a bipartite planar embedding in the sense that the vertices are located in two lines, then the graph is tree and isomorphism is easy. $\endgroup$ – Laakeri Feb 3 at 20:59
  • 2
    $\begingroup$ There is $O(n \log n)$ algorithm to check whether two given planar graphs are isomorphic or not. See paper given by J. E. HopcroftR. E. Tarjan link.springer.com/chapter/10.1007%2F978-1-4684-2001-2_13 $\endgroup$ – Shiv Feb 4 at 6:47

Your Answer

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

Browse other questions tagged or ask your own question.