Thursday, May 17, 2012

Topologically non-planar molecules

Chemists and mathematicians interpret "non-planar" differently. Very few small molecular graphs are non-planar, in the mathematical sense. Still, they do exist. In this essay, I managed to find some in the PubChem database.


nlskrg said...

Is there an article stating that MCS is solvable in polynomial-time for planar molecular graphs? The subgraph isomorphism problem is NP-complete even for connected planar graphs of bounded-degree. Hence, planarity (also combined with the bounded-degree property of molecular graphs) seems not be sufficient to attain a polynomial-time MCS algorithm (unless P=NP).

Andrew Dalke said...

Hi nlskrg,

Researching now, I see that the MCS is polynomial for outerplanar graphs, and for trees, but it is NP for planar graphs. One paper says "The maximum common subgraph problem is NP-hard even for planar graphs of bounded degree 3 (Garey and Johnson, 1979) "

Thanks for the correction!