On the noninterpolation of polyhedral maps (Q1332417)

The authors consider polyhedral embeddings of graphs in orientable surfaces, and show that in contrast to Duke's interpolation theorem, a graph can have polyhedral embeddings in surfaces of genera \(g\) and \(h\) without having polyhedral embeddings in the ``intermediate'' surfaces; moreover they show that the difference \(| g-h|\) can be made arbitrarily large. Similar results are obtained for nonorientable surfaces as well.