scientific article; zbMATH DE number 16301
[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.
- Bounding the size of equimatchable graphs of fixed genus
- The 2 and 3 representative projective planar embeddings
- On the uniqueness of kernels
- Transformations in closed 2-cell embeddings on surfaces preserving specified properties
- On the edge reconstruction of graphs embedded on surfaces
- Circular embedding of planar graphs in nonspherical surfaces
- Closed 2-cell embeddings of 4 cross-cap embeddable graphs
- A simple construction of high representativity triangulations
- Apex graphs with embeddings of face-width three
- On the orientable genus of graphs with bounded nonorientable genus
- Non-revisiting paths on surfaces with low genus
- On \(3\)-connected plane graphs without triangular faces
- Genus bounds for embeddings with large minimum degree and representativity
- Cubic graphs and related triangulations on orientable surfaces
- Light subgraphs of order at most 3 in large maps of minimum degree 5 on compact 2-manifolds
- Flexibility of polyhedral embeddings of graphs in surfaces
- On essential and inessential polygons in embedded graphs
- Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces
- Embedding grids in surfaces
- Planar triangulations which quadrangulate other surfaces
- The closed 2-cell embeddings of 2-connected doubly toroidal graphs
- Uniqueness and minimality of large face-width embeddings of graphs
- Planar graphs on the projective plane
- On minimum-genus embeddings
- A bijection for essentially 3-connected toroidal maps
- 1-embeddability of complete multipartite graphs on the projective plane
- The \(\mathbb{Z}_2\)-genus of Kuratowski minors
- Height, trunk and representativity of knots
- Representation for a smooth isometric mapping from a connected planar domain to a surface
- Orientable embeddings and orientable cycle double covers of projective-planar graphs
- Asymptotic enumeration and limit laws for graphs of fixed genus
- On the flexibility of toroidal embeddings
- 5-chromatic even triangulations on the Klein bottle
- Bounded face-width forces \(K_7\)-minors in orientable surfaces
- Enumeration of cubic multigraphs on orientable surfaces
- Representations of graphs and networks (coding, packings and embeddings)
- Flexibility of projective-planar embeddings
- Embedding graphs on surfaces
- scientific article; zbMATH DE number 1189353 (Why is no real title available?)
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Bridge position and the representativity of spatial graphs
- Algorithms for the edge-width of an embedded graph
- Almost all rooted maps have large representativity
- Hamiltonicity of 5‐Connected Toroidal Triangulations
- Face-width of Pfaffian braces and polyhex graphs on surfaces
- On zero-one and convergence laws for graphs embeddable on a fixed surface
- The $\mathbb{Z}_2$-genus of Kuratowski minors
- Generating polyhedral quadrangulations of the projective plane
- scientific article; zbMATH DE number 969111 (Why is no real title available?)
- scientific article; zbMATH DE number 2230307 (Why is no real title available?)
- Regular maps on surfaces with large planar width
- Another approach to planar cover conjecture focusing on rotation systems
- Strong log-convexity of genus sequences
- Integer programs with bounded subdeterminants and two nonzeros per row
- Scaffold for the polyhedral embedding of cubic graphs
- Two local and one global properties of 3-connected graphs on compact 2-dimensional manifolds
- On delta-wye reducibility of toroidal graphs
- Generating locally-cyclic triangulations of surfaces
- The distinguishing numbers of graphs on closed surfaces
- Graphs that triangulate a given surface and quadrangulate another surface
- Light stars in large polyhedral maps on surfaces
- Strong embedding of HP-graphs on surface with higher genus
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972954)
