Canonical decompositions and algorithmic recognition of spatial graphs

We prove that there exists an algorithm for determining whether two piecewise-linear spatial graphs are isomorphic. In its most general form, our theorem applies to spatial graphs furnished with vertex colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit cano...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the Edinburgh Mathematical Society 2024-05, Vol.67 (2), p.388-430
Main Authors: Friedl, Stefan, Munser, Lars, Quintanilha, José Pedro, Santos Rego, Yuri
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Decomposition
Forests
Graph coloring
Graphs
Neighborhoods
Spheres
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c269t-35f4767ede6b701efcf36aeb8b071fcc3cfa8385a153bfed20c6fe33a4ce564f3
container_end_page 430
container_issue 2
container_start_page 388
container_title Proceedings of the Edinburgh Mathematical Society
container_volume 67
creator Friedl, Stefan
Munser, Lars
Quintanilha, José Pedro
Santos Rego, Yuri
description We prove that there exists an algorithm for determining whether two piecewise-linear spatial graphs are isomorphic. In its most general form, our theorem applies to spatial graphs furnished with vertex colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit canonical decompositions into blocks, that is, spatial graphs that are non-split and have no cut vertices, in a suitable topological sense. Then, we apply a result of Haken and Matveev in order to algorithmically distinguish these blocks.
doi_str_mv 10.1017/S0013091524000087
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_3055290993</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><cupid>10_1017_S0013091524000087</cupid><sourcerecordid>3055290993</sourcerecordid><originalsourceid>FETCH-LOGICAL-c269t-35f4767ede6b701efcf36aeb8b071fcc3cfa8385a153bfed20c6fe33a4ce564f3</originalsourceid><addsrcrecordid>eNp1kLFOwzAQhi0EEqHwAGyRmAN2LraTEVWUIlViAObo4tipqyYOdjrw9ji0EgPilhu-_7uTfkJuGb1nlMmHN0oZ0IrxvKBxSnlGElaIIoMSqnOSzDib-SW5CmEXI1JylpDVEgc3WIX7tNXK9aMLdrJuCCkObYr7znk7bXurUh9xN_zA1Jk0jDjZaHUex224JhcG90HfnPaCfKye3pfrbPP6_LJ83GQqF9WUATeFFFK3WjSSMm2UAYG6KRsqmVEKlMESSo6MQ2N0m1MljAbAQmkuCgMLcne8O3r3edBhqnfu4If4sgbKeV7RqoKYYseU8i4Er009etuj_6oZree66j91RQdODvaNt22nf0__b30DfgltYw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>3055290993</pqid></control><display><type>article</type><title>Canonical decompositions and algorithmic recognition of spatial graphs</title><source>Cambridge University Press</source><creator>Friedl, Stefan ; Munser, Lars ; Quintanilha, José Pedro ; Santos Rego, Yuri</creator><creatorcontrib>Friedl, Stefan ; Munser, Lars ; Quintanilha, José Pedro ; Santos Rego, Yuri</creatorcontrib><description>We prove that there exists an algorithm for determining whether two piecewise-linear spatial graphs are isomorphic. In its most general form, our theorem applies to spatial graphs furnished with vertex colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit canonical decompositions into blocks, that is, spatial graphs that are non-split and have no cut vertices, in a suitable topological sense. Then, we apply a result of Haken and Matveev in order to algorithmically distinguish these blocks.</description><identifier>ISSN: 0013-0915</identifier><identifier>EISSN: 1464-3839</identifier><identifier>DOI: 10.1017/S0013091524000087</identifier><language>eng</language><publisher>Cambridge, UK: Cambridge University Press</publisher><subject>Algorithms ; Apexes ; Decomposition ; Forests ; Graph coloring ; Graphs ; Neighborhoods ; Spheres</subject><ispartof>Proceedings of the Edinburgh Mathematical Society, 2024-05, Vol.67 (2), p.388-430</ispartof><rights>The Author(s), 2024. Published by Cambridge University Press on Behalf of The Edinburgh Mathematical Society</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c269t-35f4767ede6b701efcf36aeb8b071fcc3cfa8385a153bfed20c6fe33a4ce564f3</cites><orcidid>0000-0001-5653-5811 ; 0000-0003-4821-5521 ; 0000-0001-6636-3400 ; 0000-0001-6321-7782</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.cambridge.org/core/product/identifier/S0013091524000087/type/journal_article$$EHTML$$P50$$Gcambridge$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,72960</link.rule.ids></links><search><creatorcontrib>Friedl, Stefan</creatorcontrib><creatorcontrib>Munser, Lars</creatorcontrib><creatorcontrib>Quintanilha, José Pedro</creatorcontrib><creatorcontrib>Santos Rego, Yuri</creatorcontrib><title>Canonical decompositions and algorithmic recognition of spatial graphs</title><title>Proceedings of the Edinburgh Mathematical Society</title><addtitle>Proceedings of the Edinburgh Mathematical Society</addtitle><description>We prove that there exists an algorithm for determining whether two piecewise-linear spatial graphs are isomorphic. In its most general form, our theorem applies to spatial graphs furnished with vertex colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit canonical decompositions into blocks, that is, spatial graphs that are non-split and have no cut vertices, in a suitable topological sense. Then, we apply a result of Haken and Matveev in order to algorithmically distinguish these blocks.</description><subject>Algorithms</subject><subject>Apexes</subject><subject>Decomposition</subject><subject>Forests</subject><subject>Graph coloring</subject><subject>Graphs</subject><subject>Neighborhoods</subject><subject>Spheres</subject><issn>0013-0915</issn><issn>1464-3839</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><recordid>eNp1kLFOwzAQhi0EEqHwAGyRmAN2LraTEVWUIlViAObo4tipqyYOdjrw9ji0EgPilhu-_7uTfkJuGb1nlMmHN0oZ0IrxvKBxSnlGElaIIoMSqnOSzDib-SW5CmEXI1JylpDVEgc3WIX7tNXK9aMLdrJuCCkObYr7znk7bXurUh9xN_zA1Jk0jDjZaHUex224JhcG90HfnPaCfKye3pfrbPP6_LJ83GQqF9WUATeFFFK3WjSSMm2UAYG6KRsqmVEKlMESSo6MQ2N0m1MljAbAQmkuCgMLcne8O3r3edBhqnfu4If4sgbKeV7RqoKYYseU8i4Er009etuj_6oZree66j91RQdODvaNt22nf0__b30DfgltYw</recordid><startdate>20240501</startdate><enddate>20240501</enddate><creator>Friedl, Stefan</creator><creator>Munser, Lars</creator><creator>Quintanilha, José Pedro</creator><creator>Santos Rego, Yuri</creator><general>Cambridge University Press</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0001-5653-5811</orcidid><orcidid>https://orcid.org/0000-0003-4821-5521</orcidid><orcidid>https://orcid.org/0000-0001-6636-3400</orcidid><orcidid>https://orcid.org/0000-0001-6321-7782</orcidid></search><sort><creationdate>20240501</creationdate><title>Canonical decompositions and algorithmic recognition of spatial graphs</title><author>Friedl, Stefan ; Munser, Lars ; Quintanilha, José Pedro ; Santos Rego, Yuri</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c269t-35f4767ede6b701efcf36aeb8b071fcc3cfa8385a153bfed20c6fe33a4ce564f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Algorithms</topic><topic>Apexes</topic><topic>Decomposition</topic><topic>Forests</topic><topic>Graph coloring</topic><topic>Graphs</topic><topic>Neighborhoods</topic><topic>Spheres</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Friedl, Stefan</creatorcontrib><creatorcontrib>Munser, Lars</creatorcontrib><creatorcontrib>Quintanilha, José Pedro</creatorcontrib><creatorcontrib>Santos Rego, Yuri</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Proceedings of the Edinburgh Mathematical Society</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Friedl, Stefan</au><au>Munser, Lars</au><au>Quintanilha, José Pedro</au><au>Santos Rego, Yuri</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Canonical decompositions and algorithmic recognition of spatial graphs</atitle><jtitle>Proceedings of the Edinburgh Mathematical Society</jtitle><addtitle>Proceedings of the Edinburgh Mathematical Society</addtitle><date>2024-05-01</date><risdate>2024</risdate><volume>67</volume><issue>2</issue><spage>388</spage><epage>430</epage><pages>388-430</pages><issn>0013-0915</issn><eissn>1464-3839</eissn><abstract>We prove that there exists an algorithm for determining whether two piecewise-linear spatial graphs are isomorphic. In its most general form, our theorem applies to spatial graphs furnished with vertex colourings, edge colourings and/or edge orientations. We first show that spatial graphs admit canonical decompositions into blocks, that is, spatial graphs that are non-split and have no cut vertices, in a suitable topological sense. Then, we apply a result of Haken and Matveev in order to algorithmically distinguish these blocks.</abstract><cop>Cambridge, UK</cop><pub>Cambridge University Press</pub><doi>10.1017/S0013091524000087</doi><tpages>43</tpages><orcidid>https://orcid.org/0000-0001-5653-5811</orcidid><orcidid>https://orcid.org/0000-0003-4821-5521</orcidid><orcidid>https://orcid.org/0000-0001-6636-3400</orcidid><orcidid>https://orcid.org/0000-0001-6321-7782</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0013-0915
ispartof Proceedings of the Edinburgh Mathematical Society, 2024-05, Vol.67 (2), p.388-430
issn 0013-0915
1464-3839
language eng
recordid cdi_proquest_journals_3055290993
source Cambridge University Press
subjects Algorithms
Apexes
Decomposition
Forests
Graph coloring
Graphs
Neighborhoods
Spheres
title Canonical decompositions and algorithmic recognition of spatial graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T18%3A44%3A02IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Canonical%20decompositions%20and%20algorithmic%20recognition%20of%20spatial%20graphs&rft.jtitle=Proceedings%20of%20the%20Edinburgh%20Mathematical%20Society&rft.au=Friedl,%20Stefan&rft.date=2024-05-01&rft.volume=67&rft.issue=2&rft.spage=388&rft.epage=430&rft.pages=388-430&rft.issn=0013-0915&rft.eissn=1464-3839&rft_id=info:doi/10.1017/S0013091524000087&rft_dat=%3Cproquest_cross%3E3055290993%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c269t-35f4767ede6b701efcf36aeb8b071fcc3cfa8385a153bfed20c6fe33a4ce564f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=3055290993&rft_id=info:pmid/&rft_cupid=10_1017_S0013091524000087&rfr_iscdi=true