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

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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.

Original language	English
Title of host publication	2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
Editors	Suresh Venkatasubramanian, Rasmus Pagh
Publisher	Society for Industrial and Applied Mathematics
Publication date	2018
Pages	154-168
ISBN (Electronic)	9781611975055
DOIs	https://doi.org/10.1137/1.9781611975055.14
Publication status	Published - 2018
Event	20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 - New Orleans, United States Duration: 7. Jan 2018 → 8. Jan 2018

Conference

Conference	20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
Country/Territory	United States
City	New Orleans
Period	07/01/2018 → 08/01/2018

Documents & Links

10.1137/1.9781611975055.14

1 Ph.D. thesis

Graph Theoretical Problems in Life Sciences
Nøjgaard, N., Apr 2020, Syddansk Universitet. Det Naturvidenskabelige Fakultet. 219 p.
Research output: Thesis › Ph.D. thesis

Cite this

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. In S. Venkatasubramanian, & R. Pagh (Eds.), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 (pp. 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. in S Venkatasubramanian & R Pagh (eds), 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. Society for Industrial and Applied Mathematics, pp. 154-168, 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, United States, 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. ed. / Suresh Venkatasubramanian; Rasmus Pagh. Society for Industrial and Applied Mathematics, 2018. p. 154-168.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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 -

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

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

Abstract

Conference

Documents & Links

Fingerprint

Related research output

Graph Theoretical Problems in Life Sciences

Cite this