## Abstract

We prove Sachs’ conjecture that a graph can be embedded in 3-space so that it contains no non-trivial link (in the sense of knot theory) if and only if it contains as a minor none of the seven graphs obtainable from K_{6} by Y - Δ and Δ - Y exchanges. We also show the following: (i) A graph admits such a “linkless” embedding if and only if it admits a "panelled" embedding, one such that every circuit of the graph bounds a disc disjoint from the remainder of the graph. This was a conjecture of Böhme. (ii) An embedding is panelled if and only if for every subgraph, its complement in 3-space has free fundamental group. This extends a theorem of Scharlemann and Thompson, who proved it for planar graphs. (iii) If two panelled embeddings of the same graph are “different,” that is, are not related by an orientation-preserving homeomorphism of the 3-space, then there is a subgraph which is a subdivision of K_{5} or K_{3, 3} such that the two induced embeddings of this subgraph are still different.

Original language | English (US) |
---|---|

Pages (from-to) | 185-227 |

Number of pages | 43 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 64 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 1995 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics