Graph theory & patent applications

Recognising structure.
Exploring equivalence.

Algorithms for recognising equivalent graphs, from highly symmetric structures to molecular representations.

The graph isomorphism question

Two graphs may look different or use different vertex labels while describing exactly the same connections. Graph isomorphism asks whether a one-to-one correspondence between their vertices preserves every connection.

My research explores methods for identifying this equivalence, including difficult symmetric graph families. Related work addresses unique atom labelling and the representation of chemical compounds. These are continuing research efforts; the application titles below describe the scope claimed in the filings.

From symmetry to molecular identity

Johnson graphs, generalised Johnson graphs and strongly regular graphs provide structured settings in which to explore the challenge of recognising equivalent connectivity. The research asks how structural information can help distinguish vertices and compare graphs.

For molecular graphs, a related problem is assigning atoms consistent, unique labels. Such representations can support comparisons of chemical structures independently of the order in which atoms are recorded.

2016 · Application 201611009948

Identifying isomorphs of Johnson and strongly regular graphs

A method and system proposing identification in polynomial time for the graph families named in the application.

University-listed status: Abandoned under section 21(1).

2016 · Application 201611016061

Identifying isomorphs of generalised Johnson graphs

A related method and system proposing polynomial-time identification within this graph family.

University-listed status: Abandoned under section 21(1).

2019 · Application 201911018211 A

Assigning unique labels to atoms in a chemical compound

Connecting graph representations with the identification and labelling of atoms in molecules.

University-listed status: Deemed withdrawn under section 11B(4).