The structure and labelled enumeration of K_3,3-subdivision-free projective-planar graphs
<|reference_start|>The structure and labelled enumeration of K_3,3-subdivision-free projective-planar graphs: We consider the class F of 2-connected non-planar K_{3,3}-subdivision-free graphs that are embeddable in the projective plane. We show that these graphs admit a unique decomposition as a graph K_5 (the core) where the edges are replaced by two-pole networks constructed from 2-connected planar graphs. A method to enumerate these graphs in the labelled case is described. Moreover, we enumerate the homeomorphically irreducible graphs in F and homeomorphically irreducible 2-connected planar graphs. Particular use is made of two-pole directed series-parallel networks. We also show that the number m of edges of graphs in F with n vertices satisfies the bound m <=3n-6, for n >= 6.<|reference_end|>
@article{gagarin2004the,
    title={The structure and labelled enumeration of K_{3,3}-subdivision-free
  projective-planar graphs},
    author={Andrei Gagarin, Gilbert Labelle and Pierre Leroux (LaCIM, Universite
  du Quebec a Montreal)},
    journal={Pure Math. Appl. 16 (2005), no. 3, pp. 267-286},
    year={2004},
    archivePrefix={arXiv},
    eprint={math/0406140},
    primaryClass={math.CO cs.DM}
}