Sewing ribbons on graphs in space (Q1850620)

An open (resp. closed) ribbon is a square (resp. a cylinder) with one distinguished edge (resp. boundary component) called a seam. The following problem is studied in the paper: For a given graph \(G\) a ribbon complex is formed by sewing ribbons onto \(G\). An open (resp. closed) ribbon is sewn to \(G\) along an open (resp. closed) walk. Then the question arises: When is such a ribbon complex embeddable into 3-space? The first main result of the paper states that a ribbon complex is spatial if and only if a certain corresponding labeled graph is planar. The second main result states that there is a polynomial-time algorithm to determine planarity for the class of labeled graphs with maximum degree three. Furthermore, the minimal nonspatial ribbon complexes are studied, and a characterization of them is found under the assumption that at most three ribbons can meet at an edge. The paper gives an interesting connection between graph theory, topology, and algorithms in discrete mathematics.