4
$\begingroup$

Given a graph $G$, there is a minimal integer $g$ associated with it which captures the minimum genus a surface needs to have so that $G$ embeds in the surface without edge crossings.

  1. Is there a way to define non-equivalent embeddings?

  2. Are there any bounds on the number non-equivalent embeddings?

  3. If all embeddings are unique up to some symmetry, is there a way to see this?

Are there any references on embedding equivalence?

$\endgroup$

2 Answers 2

6
$\begingroup$

Ad 1. One notion of two embeddings being equivalent is "there exists an ambient isotopy carrying the image of one embedding onto the image of the other". Another, stronger, notion, more usual in the literature on topological graph theory is "embeddings $\eta_0$ and $\eta_1$ equivalent if and only if there exists a homeomorphism $h\colon S\rightarrow S$ of the surface to itself, such that $\eta_0\circ h = \eta_1$, as set-maps.

Ad 2. For one thing, in general, for an $n$-vertex graph there is the trivial upper bound $\prod_{i\in n} (\mathrm{deg}_G(v_i)-1)!$ which is explained by an embedding being characterized by combinatorially data in terms of the $V(G)$-indexed sequence of cyclic orders on the sets of edges incident with the indexing vertex. Usually, this upper bound is far too large; many of the data usually correspond to the same embedding. Specifically, there are several non-trivial results. One is S. Kitakubo: Bounding the number of embeddings of 5-connected projective-planar graphs. J. Graph Theory 15 (1991), 199-206 wherein a proof is given of an upper bound, to the effect that w.r.t. the above notion of embedding-equivalence there is an absolute bound of 120 for the number of inequivalent embeddings, when this functions ranges over the class of all vertex-5-connected graphs which are embeddable into the projective plane.

Ad 3: would you please clarify what you mean? Do you mean it in the sense of a decision problem? Neither of "symmetry", nor "to see" is clear, nor is it clear whether you consider the genus part of the input of the decision problem is clear. More generally, the whole intended logical structure of your question 2. is unclear. Would you please clarify what you mean here?

Ad your last question: there are many. You might like to start with the work of Shigeru Kitakubo and Seiya Negami.

$\endgroup$
2
$\begingroup$

Peter Heinig's answer is excellent, but here are some further remarks:

  1. Under the "ambient isotopy" definition, there are infinitely many classes of embeddings (because the mapping class group is infinite), except in genus $0.$

  2. In genus $0,$ if the graph is $3$-connected, there are exactly two embeddings (which are equivalent if you allow orientation-reversing flips). This is a celebrated theorem of H. Whitney.

  3. Re symmetries, you should check out the 1994 paper of Kwak and Lee.

Kwak, Jin Ho; Lee, Jaeun, Enumeration of graph embeddings, Discrete Math. 135, No.1-3, 129-151 (1994). ZBL0813.05034.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.