Linkless embeddings of graphs in 3-space

Neil Robertson, P. D. Seymour, Robin Thomas

Research output: Contribution to journalComment/debatepeer-review

33 Scopus citations

Abstract

We announce results about flat (linkless) embeddings of graphs in 3-space. A piecewise-linear embedding of a graph in 3-space is called flat if every circuit of the graph bounds a disk disjoint from the rest of the graph. We have shown: (i) An embedding is flat if and only if the fundamental group of the complement in 3-space of the embedding of every subgraph is free. (ii) If two flat embeddings of the same graph are not ambient isotopic, then they differ on a subdivision of K5 or K3,3. (iii) Any flat embedding of a graph can be transformed to any other flat embedding of the same graph by “3-switches”, an analog of 2-switches from the theory of planar embeddings. In particular, any two flat embeddings of a 4-connected graph are either ambient isotopic, or one is ambient isotopic to a mirror image of the other. (iv) A graph has a flat embedding if and only if it has no minor isomorphic to one of seven specified graphs. These are the graphs that can be obtained from K6 by means of Y∆- and ∆Y-exchanges.

Original languageEnglish (US)
Pages (from-to)84-89
Number of pages6
JournalBulletin of the American Mathematical Society
Volume28
Issue number1
DOIs
StatePublished - Jan 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Linkless embeddings of graphs in 3-space'. Together they form a unique fingerprint.

Cite this