1
$\begingroup$

I am trying to find a function / algorithm that will search and find a mapping between an irregular graph (say, N-nodes with maximum vertex degree-K but otherwise irregular) into a regular L-nearest neighbor graph with also N-nodes. I know that if L equals N, there is a trivial mapping where we simply place the irregular graph into this complete graph and disconnect all the unnecessary connections.

This comes very close to FindGraphIsomorphism but it isn't quite that since GraphIsomorphism looks for exact mappings between two graphs, here I am simply looking for an embedding.

Is there an easy function known for this purpose that I don't know?

Thanks in advance.

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure if such a thing is in mathematica already, but you might find @Szabolcs' wonderful IGraph package useful; possibly the function IGGetSubisomorphism in particular, which seems to find a mapping that realizes its first argument as a subgraph of its second argument (if such a mapping exists). (Disclosure: I haven't had occasion to use it myself, so I'm just going off of my interpretation of the documentation.) $\endgroup$
    – thorimur
    Sep 18, 2021 at 21:57
  • $\begingroup$ Yes, I think this is exactly what I needed, thank you. $\endgroup$
    – anon248
    Sep 18, 2021 at 23:29

1 Answer 1

4
$\begingroup$

As an answer from @thorumur's comment:

You might find Szabolcs' wonderful IGraph package useful, possibly the function IGGetSubisomorphism in particular, which (from the documentation) seems to find a mapping that realizes its first argument as a subgraph of its second argument if such a mapping exists.

$\endgroup$

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.