Re: [Rdkit-discuss] question on complexity of cannonization

Planar graphs are... In graph theory , a *planar graph* is a graph that can be embedded in the plane

Re: [Rdkit-discuss] question on complexity of cannonization

On 16/06/2023 03:49, S Joshua Swamidass wrote: Incidentally, I came across this O(log N) canonization algorithm for planar graphs: https://arxiv.org/pdf/0809.2319.pdf I wonder if this algorithm can be adapted for chemistry? Molecules are usually planar, but I believe they occasionally are

Re: [Rdkit-discuss] question on complexity of cannonization

On Jun 15, 2023, at 20:49, S Joshua Swamidass wrote: > > And what (generally speaking) is the algorithm used by rdkit? Do we know it's > complexity? https://pubs.acs.org/doi/abs/10.1021/acs.jcim.5b00543 "Get Your Atoms in Order—An Open-Source Implementation of a Novel and Robust Molecular

Re: [Rdkit-discuss] question on complexity of cannonization

Well, if I'm recalling correctly, a highly symmetric structure like buckminsterfullerene takes a long time to canonicalize. I don't know what the formal definition of a planar graph is, but I would guess it's not what chemists mean when they say a molecule is planar. -P. On Thu, Jun 15, 2023 at

Re: [Rdkit-discuss] question on complexity of cannonization

Incidentally, I came across this O(log N) canonization algorithm for planar graphs: https://arxiv.org/pdf/0809.2319.pdf I wonder if this algorithm can be adapted for chemistry? Molecules are usually planar, but I believe they occasionally are "nearly" planar, by which I mean planar graphs plus a

Re: [Rdkit-discuss] question on complexity of cannonization

Andrew, Thanks! According to wikipedia (and my recollections of algorithms class)... "The problem is not known to be solvable in polynomial time nor to be NP-complete , and therefore may be in the

Re: [Rdkit-discuss] question on complexity of cannonization

On Jun 15, 2023, at 18:20, S Joshua Swamidass wrote: > It's well known that the graph-isomorphism problem is NP While P is contained in NP, I don't think that's the NP you mean. I suspect you may be thinking of subgraph isomorphism, which is NP-hard. Graph isomorphism may be quasi-polynomial

[Rdkit-discuss] question on complexity of cannonization

Hello, I had a theoretical question I thought the RDkit team might have some insight on. It's well known that the graph-isomorphism problem is NP, which means that for some examples run-time will be worse than polynomial using known algorithms. This problem is connected to molecule canonization.