1
$\begingroup$

I am trying to find an example for the Theorem 5.1 of the paper "Combinatorial Local Planarity and the Width of Graph Embeddings" that can be found at http://www.fmf.uni-lj.si/~mohar/Reprints/1992/BM91_CJM44_Mohar_GraphEmbeddings.pdf. Given G(V,E) minimally embeddable on an orientable surface $\Sigma_g$ of genus $g \geq 2$. Suppose that $C_1,C_2,\ldots, C_k$ be a planarly nested sequence (defined below) and $k\leq g$. I am trying to construct an example for graphs of genus $g \geq 2$ and $ k = g$ in which none of $C_1,C_2,\ldots, C_k$ bounds disks.

Definition: A sequence of disjoint cycles $C_1,C_2, \ldots, C_k$ is planarly nested if each cycle $C_i (1 \leq i \leq k)$ has a relative $C_i$ component $H_i$ such that $H_1 \supset H_2 \supset \ldots \supset H_k$ and the graph obtained from $G$ by contracting to a single vertex all edges in the relative component $H_k$, except it feet, is planar.

A relative $C$-component for a cycle $C$ is an edge $e \in E(G)\backslash E(C)$ with both endpoint in $C$, or a connected component of $V(G) - V(C)$ together with all edges between this component and $C$. Edge of a $C$-component $R$ having an endpoint in $C$ is a foot of $R$.

Here is an example of two relatives $C$-component $H_1$ and $H_2$ of G. enter image description here

Improve this question
$\endgroup$
  • $\begingroup$ Just consider an embedded $K_5$ and one of its noncontractible cycles, $C_1$. There is an edge $e\in H_1$ which is not a foot of $H_1$, but contracting this edge leaves the graph planar. $\endgroup$ – Saeed Jan 19 '15 at 13:51
  • $\begingroup$ Thanks for your answer. Maybe you misunderstand my question. I need an example in which the surface has $g\geq 2$ ($g=2$ for double torus) and the sequences of cycles (at least 2) are all non-contractible. It is easy to find and example for graphs embeddable on the torus. I should add this to the questions. $\endgroup$ – Hung Le Jan 19 '15 at 18:31
  • $\begingroup$ Sorry but I didn't misunderstood the question, you just edited the question and added $k=g$. How can I guess the size of sequence of cycles should be g? why using k? but for genus 1000 consider embedded k_5 as above and attach a graph of genus 999 to a vertex that does not belong to $C_1$. I didn't wrote this because I thought maybe you cannot find any so after that it's trivial. Anyhow I'll think a little bit for your new criteria, if I find something I'll write. $\endgroup$ – Saeed Jan 19 '15 at 19:02
  • $\begingroup$ I see! That's my mistake for not being clarified enough. I included k since the theorem states that for any $k \leq g$, you can find such a non-disk-bounding planarly nested sequence. For me, it is interesting to find a sequence when $k = g$ and $g\geq 2$. $\endgroup$ – Hung Le Jan 19 '15 at 19:09
  • $\begingroup$ Can you tell me where is the exact definition of relative component in the paper? I just read one page where the theorrm is there definition of those cycle were there but not definition of relative component. Also I think 1 <k <g+1 is important for you not necessarily k=g. $\endgroup$ – Saeed Jan 22 '15 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.