Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings

Marc Hellmuth; Anders S. Knudsen; Michal Kotrbík; Daniel Merkle; Nikolai Nøjgaard

doi:10.1137/1.9781611975055.14

Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings

Marc Hellmuth, Anders S. Knudsen, Michal Kotrbík, Daniel Merkle, Nikolai Nøjgaard

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

Antiparallel strong traces (ASTs) are a type of walks in graphs which use every edge exactly twice. They correspond to 1-face embeddings in orientable surfaces and can be used to design self-assembling protein or DNA strands. Based on a novel canonical form invariant for ASTs, gap vector, we provide a linear-time isomorphism test for ASTs and thus, also for orientable 1-face embeddings of graphs. Using the canonical form, we develop an algorithm for enumerating all pairwise non-isomorphic 1-face embeddings of graphs. We compare our algorithm with an independent implementation of a recent algebraic approach (Baši? et al., MATCH Commun. Math. Comput. Chem. 78 (3), 2017) on large data sets. Our results yield the first large-scale enumeration of non-isomorphic embeddings and investigation of their properties.

Originalsprog	Engelsk
Titel	2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
Redaktører	Suresh Venkatasubramanian, Rasmus Pagh
Forlag	Society for Industrial and Applied Mathematics
Publikationsdato	2018
Sider	154-168
ISBN (Elektronisk)	9781611975055
DOI	https://doi.org/10.1137/1.9781611975055.14
Status	Udgivet - 2018
Begivenhed	20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 - New Orleans, USA Varighed: 7. jan. 2018 → 8. jan. 2018

Konference

Konference	20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
Land/Område	USA
By	New Orleans
Periode	07/01/2018 → 08/01/2018

Dokumenter og links

10.1137/1.9781611975055.14

1 Ph.d.-afhandling

Graph Theoretical Problems in Life Sciences
Nøjgaard, N., apr. 2020, Syddansk Universitet. Det Naturvidenskabelige Fakultet. 219 s.
Publikation: Afhandling › Ph.d.-afhandling

Citationsformater

Hellmuth, M., Knudsen, A. S., Kotrbík, M., Merkle, D., & Nøjgaard, N. (2018). Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings. I S. Venkatasubramanian, & R. Pagh (red.), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 (s. 154-168). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975055.14

@inproceedings{c2d7dd3b886046b987f557c052a8a017,

title = "Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings",

abstract = "Antiparallel strong traces (ASTs) are a type of walks in graphs which use every edge exactly twice. They correspond to 1-face embeddings in orientable surfaces and can be used to design self-assembling protein or DNA strands. Based on a novel canonical form invariant for ASTs, gap vector, we provide a linear-time isomorphism test for ASTs and thus, also for orientable 1-face embeddings of graphs. Using the canonical form, we develop an algorithm for enumerating all pairwise non-isomorphic 1-face embeddings of graphs. We compare our algorithm with an independent implementation of a recent algebraic approach (Ba{\v s}i? et al., MATCH Commun. Math. Comput. Chem. 78 (3), 2017) on large data sets. Our results yield the first large-scale enumeration of non-isomorphic embeddings and investigation of their properties.",

author = "Marc Hellmuth and Knudsen, {Anders S.} and Michal Kotrb{\'i}k and Daniel Merkle and Nikolai N{\o}jgaard",

year = "2018",

doi = "10.1137/1.9781611975055.14",

language = "English",

pages = "154--168",

editor = "Suresh Venkatasubramanian and Rasmus Pagh",

booktitle = "2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 ; Conference date: 07-01-2018 Through 08-01-2018",

}

Hellmuth, M, Knudsen, AS, Kotrbík, M, Merkle, D & Nøjgaard, N 2018, Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings. i S Venkatasubramanian & R Pagh (red), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. Society for Industrial and Applied Mathematics, s. 154-168, 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, USA, 07/01/2018. https://doi.org/10.1137/1.9781611975055.14

Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings. / Hellmuth, Marc; Knudsen, Anders S.; Kotrbík, Michal et al.
2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. red. / Suresh Venkatasubramanian; Rasmus Pagh. Society for Industrial and Applied Mathematics, 2018. s. 154-168.

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings

AU - Hellmuth, Marc

AU - Knudsen, Anders S.

AU - Kotrbík, Michal

AU - Merkle, Daniel

AU - Nøjgaard, Nikolai

PY - 2018

Y1 - 2018

N2 - Antiparallel strong traces (ASTs) are a type of walks in graphs which use every edge exactly twice. They correspond to 1-face embeddings in orientable surfaces and can be used to design self-assembling protein or DNA strands. Based on a novel canonical form invariant for ASTs, gap vector, we provide a linear-time isomorphism test for ASTs and thus, also for orientable 1-face embeddings of graphs. Using the canonical form, we develop an algorithm for enumerating all pairwise non-isomorphic 1-face embeddings of graphs. We compare our algorithm with an independent implementation of a recent algebraic approach (Baši? et al., MATCH Commun. Math. Comput. Chem. 78 (3), 2017) on large data sets. Our results yield the first large-scale enumeration of non-isomorphic embeddings and investigation of their properties.

AB - Antiparallel strong traces (ASTs) are a type of walks in graphs which use every edge exactly twice. They correspond to 1-face embeddings in orientable surfaces and can be used to design self-assembling protein or DNA strands. Based on a novel canonical form invariant for ASTs, gap vector, we provide a linear-time isomorphism test for ASTs and thus, also for orientable 1-face embeddings of graphs. Using the canonical form, we develop an algorithm for enumerating all pairwise non-isomorphic 1-face embeddings of graphs. We compare our algorithm with an independent implementation of a recent algebraic approach (Baši? et al., MATCH Commun. Math. Comput. Chem. 78 (3), 2017) on large data sets. Our results yield the first large-scale enumeration of non-isomorphic embeddings and investigation of their properties.

U2 - 10.1137/1.9781611975055.14

DO - 10.1137/1.9781611975055.14

M3 - Article in proceedings

AN - SCOPUS:85041384256

SP - 154

EP - 168

BT - 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018

A2 - Venkatasubramanian, Suresh

A2 - Pagh, Rasmus

PB - Society for Industrial and Applied Mathematics

T2 - 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018

Y2 - 7 January 2018 through 8 January 2018

ER -

Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings

Abstract

Konference

Dokumenter og links

Fingeraftryk

Relaterede publikationer

Graph Theoretical Problems in Life Sciences

Citationsformater