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

[S J. S. <swa...@gm...>]

Planar graphs are...

In graph theory <https://en.wikipedia.org/wiki/Graph_theory>, a *planar
graph* is a graph
<https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)> that can be
embedded <https://en.wikipedia.org/wiki/Graph_embedding> in the plane
<https://en.wikipedia.org/wiki/Plane_(geometry)>, i.e., it can be drawn on
the plane in such a way that its edges intersect only at their endpoints.
In other words, it can be drawn in such a way that no edges cross each
other.
https://en.wikipedia.org/wiki/Planar_graph

We aren't talking about whether or not the chemical structure is 2D or 3D.
Molecules representable as planar graphs can certainly be 3D molecules that
do not have planar structures. For example, cyclohexane is not a planar
molecule (vs. benzene for example), but it can trivally be drawn in 2D
without any crossing bonds. Likewise, (if ignore disulfide bonds and other
gotchas), the covalent bonds of proteins of arbitrary size are a planar
graph too, even though most (all?) proteins have a 3D structure.



On Thu, Jun 15, 2023 at 8:05 PM Francois Berenger <ml...@li...> wrote:

> 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 "nearly" planar,
> > by which I mean planar graphs plus a few edges that break the
> > planarity.
>
> Dear Joshua,
>
> Some natural product are notoriously complex 3D molecules.
>
> What do you exactly mean by planar?
>
> Many chemical groups are 3D: methyl, adamantane, etc.
>
> > And what (generally speaking) is the algorithm used by rdkit? Do we
> > know it's complexity?
> >
> > On Thu, Jun 15, 2023 at 1:38 PM S Joshua Swamidass
> > <swa...@gm...> wrote:
> >
> >> Andrew,
> >>
> >> Thanks! According to wikipedia (and my recollections of algorithms
> >> class)...
> >> "The problem is not known to be solvable in polynomial time [1] nor
> >> to be NP-complete [2], and therefore may be in the computational
> >> complexity class [3] NP-intermediate [4]."
> >>
> >> https://en.wikipedia.org/wiki/Graph_isomorphism_problem
> >>
> >> Your reference though is really helpful. The key phrase seems to be
> >> "bounded valence" which is certainly true of molecular graphs. Each
> >> atom can only bound some fairly low number of other atoms, i.e.
> >> bounded valence. That's probably the reason why we do have a
> >> polynomial time algorithm...
> >>
> >> Thank you!
> >>
> >> Joshua
> >>
> >> On Thu, Jun 15, 2023 at 1:21 PM Andrew Dalke
> >> <da...@da...> wrote:
> >>
> >>> On Jun 15, 2023, at 18:20, S Joshua Swamidass
> >>> <swa...@gm...> 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 time, if
> >>> Babai's (unpublished) claim is correct.
> >>>
> >>> Also, "Isomorphism of graphs of bounded valence can be tested in
> >>> polynomial time" -
> >>> https://www.sciencedirect.com/science/article/pii/0022000082900095
> >>> .
> >>>
> >>>> So here is my question. What are the cases that are very
> >>> difficult to canonize a graph?
> >>>
> >>> As I recall, handling chirality and other non-local properties is
> >>> difficult. I have not worked on this problem.
> >>>
> >>> Cheers,
> >>>
> >>> Andrew
> >>> da...@da...
> >
> >
> > Links:
> > ------
> > [1] https://en.wikipedia.org/wiki/Polynomial_time
> > [2] https://en.wikipedia.org/wiki/NP-complete
> > [3] https://en.wikipedia.org/wiki/Complexity_class
> > [4] https://en.wikipedia.org/wiki/NP-intermediate
> > _______________________________________________
> > Rdkit-discuss mailing list
> > Rdk...@li...
> > https://lists.sourceforge.net/lists/listinfo/rdkit-discuss
>