6
$\begingroup$

I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs.

I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-on-chip (the large graph).

I have already implemented Ullman's subgraph isomorphism algorithm and I'm successfully listing all valid mappings. However it is quite slow for larger inputs. After some research I found that the problem becomes easier for planar graphs. The Eppstein paper provides the mathematics behind planar subgraph isomorphism and claims $\mathcal{O}(n)$ runtime instead of $\mathcal{O}(x^n)$.

Because I don't have a strong mathematics background I was wondering if someone could provide me with:

  1. An explanation that is simpler than the attached paper of planar subgraph isomorphism. I got as far as tree decomposition but I'm finding the rest very difficult to grasp.
  2. The pseudo-code algorithm to find subgraphs in planar graphs according to the Eppstein paper, or if there is something with similar/better runtime.
$\endgroup$
6
  • 1
    $\begingroup$ This is not any simpler, but is asymptotically faster: arxiv.org/pdf/0909.4692v1.pdf, and includes a pseudocode skeleton for the algorithm, which should make implementation a little less painful. $\endgroup$ Feb 17, 2015 at 4:50
  • 1
    $\begingroup$ I also suspect that your question as it is might be a bit broad (the answers would be quite long). If you can break it down into a series of separate questions (not all in one go, just as you get to tricky parts), the problem might be a bit more tractable (both for your understanding and for those trying to answer). $\endgroup$ Feb 17, 2015 at 4:53
  • 2
    $\begingroup$ keep in mind some of these advanced theoretical algorithms have never been actually implemented and may not actually even be practical even despite the complexity bounds.... $\endgroup$
    – vzn
    Feb 17, 2015 at 16:20
  • $\begingroup$ @vzn Yes, I'm starting to see that. My hope that is difficult to implement but not impossible. $\endgroup$
    – mohsaied
    Feb 17, 2015 at 23:27
  • $\begingroup$ @LukeMathieson Thanks for the second paper. I came across it quickly but thought I would try understanding Eppstein's work first since it builds on it. $\endgroup$
    – mohsaied
    Feb 17, 2015 at 23:28

1 Answer 1

6
$\begingroup$

I'm not aware of any implementations of planar subgraph isomorphism algorithms, sorry. Note that "SubGemini", which is a (1993) circuit/netlist-oriented subgraph isomorphism solver, doesn't use a planar algorithm, seemingly because they did not want to make planarity assumptions.

For subgraph isomorphism in general (i.e. not planar), the practical state of the art seems to be:

All of these papers have experimental results, so you can get an idea what problem sizes they can handle (which might not be a bad idea to specify in your question).

The paper by Dorn (2009) suggested by Luke Mathieson above seems your best bet if you want to implement planar subgraph isomorphism, but that paper has no experimental results, so... you'll probably be the first to experiment with it.


Alternatively, since we're talking subcircuit extraction (SCE) here, you could look at Jiang and Bunke's Marked Subgraph Isomorphism approach for SCE. The assumption there is different than planarity:

In this case we know a priori that the degree of some vertices is preserved under the subgraph isomorphism mapping. This information is explicitly utilized to develop a polynomial-time algorithm.

I'm a bit skeptical about the applicability of that paper to real-life SCE because the paper was published at somewhat obscure workshop that is not even circuit-focused... But they claim to have soundly beaten SubGemini. The subgraphs searched there are pretty small, a 6 node cell (presumably 6T SRAM cell) is searched and found (in many copies) in a RAM array of several thousand copies. If your application looks like this... it might be what you want.

The 2003 IEEE Potentials article about SCE even though co-authored by Frank Harary alas ignores this paper of Jiang and Bunke entirely, which not really a surprise to me given where it was published. You may want to read that brief for pointers to other approaches to SCE, including genetic algorithms, neural networks etc. A couple of SCE papers indicated in that brief as claiming good practical results are:

Not covered in that review because it's slightly newer is FROSTY; it works by matching smaller directed (sub)graphs by doing a first pass identifying gates. In its paper, results are only compared to SubGemini though, which isn't that hard to beat.

Somewhat similar (in the sense that it relies on higher-level graphs that are in a certain sense directed) but broader in scope (in the sense that it handles both exact and approximate matching) is "Pattern Search in Hierarchical High-Level Designs" by Terem et al. from Intel + Moshe Vardi. The way they handle both exact and approximate matching is setting up both problems a constraint satisfaction problems.

Also probably worth looking at is a series papers by N. Rubanov 2006; 2002; his methods are probabilistic, but they all beat SubGemini by orders of magnitude. Rubanov worked in the EDA industry (Circuit Semantics, Magma Design Automation, Cadence).

There also three fairly recent Oracle (prbably Sun labs) patents by Douglas C. Meserve in this area: US7958468, US7861193, US8788990. I couldn't find any academic publication related to these patents.

The most recent comprehensive SCE work I found (insofar) is a 2009 Ph.D. thesis "Hierarchical Pattern Matching in VLSI" by M. Miloševic.

As an interesting addendum, SubGemini is based on the Conneil and Gotlieb partitioning, which has its issues, in these sense that its correctness is based on a conjecture that was eventually proved false by counterexample.

$\endgroup$
1
  • $\begingroup$ This is incredible! Thanks for all of that information. $\endgroup$
    – mohsaied
    Feb 18, 2015 at 23:09

Your Answer

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

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