On the local genus distribution of graph embeddings

zbMATH Open1371.05128arXiv1601.02574MaRDI QIDQ4977504FDOQ4977504

Authors: Ricky X. F. Chen, Christian M. Reidys 

Publication date: 16 August 2017

Abstract: The $2$-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that ($2$-cell) embedding a given graph $G$ on a closed orientable surface is equivalent to cyclically ordering the edges incident to each vertex of $G$. In this paper, we study the following problem: given a genus $g$ embedding $epsilon$ of the graph $G$ and a vertex of $G$, how many different ways of reembedding the vertex such that the resulting embedding $epsilo{n}^{\prime }$ is of genus $g+Deltag$? We give formulas to compute this quantity and the local minimal genus achieved by reembedding. In the process we obtain miscellaneous results. In particular, if there exists a one-face embedding of $G$, then the probability of a random embedding of $G$ to be one-face is at least $pro{d}_{uinV(G)}frac2deg(u)+2$, where $deg(u)$ denotes the vertex degree of $u$. Furthermore we obtain an easy-to-check necessary condition for a given embedding of $G$ to be an embedding of minimum genus.

Full work available at URL: https://arxiv.org/abs/1601.02574

Recommendations

• Distribution of embeddings
• Locally-maximal embeddings of graphs in orientable surfaces
• Orientable embedding distributions by genus for certain type of non-planar graphs. I.
• Face distributions of embeddings of complete graphs
• On the average genus of the random graph

zbMATH Keywords

genusgraph embeddinghypermapplane permutation

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Cited In (6)

• Distribution of embeddings
• Asymptotics of local face distributions and the face distribution of the complete graph
• A versatile combinatorial approach of studying products of long cycles in symmetric groups
• Combinatorially refine a Zagier-Stanley result on products of permutations
• 2-cell embeddings with prescribed face lengths and genus
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations

This page was built for publication: On the local genus distribution of graph embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977504)