No label defined (Q3972954)

[For the entire collection see Zbl 0719.00011.] A graph \(G\) is embedded on a surface \(\Sigma\) with representativity \(\rho\) if \(| G\cap C|\geq \rho\) for any noncontractible curve \(C\) in \(\Sigma\). An embedding of large representativity has the property that large neighborhoods of points in \(G\) are planar. So the ''locally Euclidean'' property of \(\Sigma\) is mirrored by the ''local planarity'' in the embedding of \(G\). Do graphs embedded with high representativity share properties with planar graphs? For example, are they 5-colorable? Hamiltonian? Are the embeddings of minimal genus? This paper serves the dual purpose of surveying known results about representativity and developing the elementary theory. General topics include: (a) recognizing embeddings with low representativity, (b) structural properties of \(G\) implied by large representative embeddings, (c) obstruction sets for small surfaces, (d) algorithmic considerations (polynomial-time algorithms for classes of graphs where the general problem is NP-complete), (e) re-embedding properties (e.g., the structure of embeddings of planar graphs on other surfaces), (f) the relationship with \(\Delta Y\)-transformations, and (g) the relationship between genus and representativity. The paper is a valuable resource for both the researchers in the field and those looking for an introductory paper. It is a welcome and highly needed addition to the literature.