An algorithm for detecting intrinsically knotted graphs

DOI10.1080/10586458.2014.852033MaRDI QIDQ5418071zbMATH OpenOpenAlexFDO

Authors Jonathan Miller, Ramin Naimi

Publication date 26 May 2014

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.1030

zbMATH Keywords

Arf invariantintrinsically knottedlinking numberspatial graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

Abstract: We describe an algorithm that recognizes some (perhaps all) intrinsically knotted (IK) graphs, and can help find knotless embeddings for graphs that are not IK. The algorithm, implemented as a Mathematica program, has already been used by Goldberg, Mattman, and Naimi [6] to greatly expand the list of known minor minimal IK graphs, and to find knotless embeddings for some graphs that had previously resisted attempts to classify them as IK or non-IK.

Recommendations

• SOME RESULTS ON INTRINSICALLY KNOTTED GRAPHS
• Intrinsic knotting and linking of almost complete graphs
• More intrinsically knotted graphs
• Intrinsically knotted graphs
• More intrinsically knotted graphs with 22 edges and the restoring method

Cites work

• A newly recognized intrinsically knotted graph
• A polynomial-time algorithm to find a linkless embedding of a graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Intrinsically knotted graphs
• Knots and links in spatial graphs
• Realization of knots and links in a spatial graph
• Sachs' linkless embedding conjecture

Cited in

(9)

• Detecting unknotted graphs in 3-space
• Many, many more intrinsically knotted graphs
• Order nine MMIK graphs
• Computing invariants of knotted graphs given by sequences of points in 3-dimensional space
• Linearly free graphs
• Complete minors in complements of nonseparating planar graphs
• Dips at small sizes for topological graph obstruction sets
• Intrinsically knotted graphs and connected domination
• The smallest bipartite intrinsically knotted graph

This page was built for publication: An algorithm for detecting intrinsically knotted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5418071)