Subscribe to:
Post Comments (Atom)

skip to main |
skip to sidebar
## Thursday, May 17, 2012

###
Topologically non-planar molecules

## About Me

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.

Subscribe to:
Post Comments (Atom)

- Andrew Dalke
- I am an American living in GĂ¶teborg, Sweden. I make my living writing software for computational chemistry and biology, usually in Python.

## 2 comments:

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).

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!

Post a Comment