Embedding Cycle Graphs Complements

Abstract

A graph is embeddable on a surface if it can be drawn on that surface without any edges intersect. The cycle graphs can always be embedded on the plane and the torus, but this is not occurred for their complements. We prove that the maximum order of cycle graphs such that their complements still can be embedded on the plane is 6. But, the maximum order of cycle graphs such that their complements still can be embedded on the torus is 9. Also, the crossing number of complements of cycle graphs which can’t be embedded on the plane with minimum order will be presented.