Re-embeddings of Maximum 1-Planar Graphs

Abstract

In this paper, we examine the re-embeddability of maximum 1-planar graphs. In particular, we prove that every optimal 1-planar graph is uniquely 1-embeddable on the sphere except for a sequence of graphs that are minimal with respect to certain reductions. These optimal 1-planar graphs are closely related to their quadrangular subgraphs. We also give a generating theorem for optimal 1-planar graphs.