FREE PLANAR GRAPHS ON TORUS
Dainis Zeps · 2004
Graph on plane, projective plane or torus is free planar if it remains embeddable in corresponding surface after arbitrary edge is added. Free planar graph is called ladder-augmentable if two edges in it may be replaced with arbitrary large ladder-graph [3] and graph will remain to be free planar with respect to surface where it is embedded. There are only two nontrivial 3-connected free planar graphs on sphere, i.e. wheel graph and envelope graph, where only the first can be unboundedly augmented with a punkah like augment [3] retaining its 3-connectivity and freeness on the sphere. Envelope graph may be augmented with ladder like augment only when it is on the Mobius strip. Similarly on torus, if 3-connected toroidal free planar graph is ladder-augmentable then it should be projective planar, except in some special cases [3], e. g. shown in Fig.1. The graph in Fig.1 is one of minimal forbidden graphs for projective plane (graph D17 in [2] and the only one which becomes planar when edge is eliminated from it). Perhaps it is the only one which is projective non-planar and free ladder-augmentable on torus. K3,3 and K5 are ladder-augmentable because they both are projective planar [3].