<p>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 <a href="http://www.fmf.uni-lj.si/~mohar/Reprints/1992/BM91_CJM44_Mohar_GraphEmbeddings.pdf" rel="nofollow noreferrer">http://www.fmf.uni-lj.si/~mohar/Reprints/1992/BM91_CJM44_Mohar_GraphEmbeddings.pdf</a>. Given G(V,E) minimally embeddable on an <strong>orientable</strong> 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. </p>

<p><strong>Definition:</strong> 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.</p>

<p>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 <strong>foot</strong> of $R$.</p>

<p>Here is an example of two relatives $C$-component $H_1$ and $H_2$ of G.
<img src="https://i.sstatic.net/apy0e.png" alt="enter image description here"></p>

CC BY-SA 3.0
2015-01-19T13:51:13.450Z
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.
Saeed
CC BY-SA 3.0
2015-01-19T18:31:19.800Z
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.
Hung Le
CC BY-SA 3.0
2015-01-19T19:02:41.633Z
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.
Saeed
CC BY-SA 3.0
2015-01-19T19:09:12.767Z
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$.
Hung Le
CC BY-SA 3.0
2015-01-22T07:53:19.007Z
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.
Saeed
CC BY-SA 3.0
2015-01-22T08:20:43.530Z
Yes! any 1 < k < g+1 is good. The definition in the paper is exactly the same that in my question above. I've added a figure to illustrate the idea of relative $C$-component
Hung Le
CC BY-SA 3.0
2015-01-22T09:45:25.163Z
I see your definition, but by this definition and your interpretation of definition I can show that there is no k non-contractible cycles for k > 1 which satisfies the condition, but my interpretation there is, so I want to see the definition of the paper and its interpretation even if they are same. In my interpretation we can take a subgraph of $H_1$ in your example above. If this is not correct then that $H_i$ cannot be relative to non-separating cycle, but if it's from a separating non-contractible cycle $C$ then as $C$ separates the graph we obtain at least two subgraphs of $g\ge 1$.
Saeed
CC BY-SA 3.0
2015-01-24T01:35:10.320Z
Hi Saeed, thank you for your comment! I originally thought like what you commented above. But I do not know why Mohar did not included such an argument to his paper, that would be a stronger statement, and of course, that also depends on how you interpret the relative component $H_i$. I asked for an example because sometimes with topology, it is intuitively clear but making a full argument is non-trivial like Jordan Curve Theorem.
Hung Le
<topology><topological-graph-theory>
Example of non-disk bounding planarly nested sequences of cycles
Hung Le
# Example of non-disk bounding planarly nested sequences of cycles

(Asked by: username_0 on 2015-01-19)

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](https://i.sstatic.net/apy0e.png)

**Tags:** topology, topological-graph-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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$.  
> **username_1**: 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.  
> **username_0**: Yes! any 1 < k < g+1 is good. The definition in the paper is exactly the same that in my question above. I've added a figure to illustrate the idea of relative $C$-component  
> **username_1**: I see your definition, but by this definition and your interpretation of definition I can show that there is no k non-contractible cycles for k > 1 which satisfies the condition, but my interpretation there is, so I want to see the definition of the paper and its interpretation even if they are same. In my interpretation we can take a subgraph of $H_1$ in your example above. If this is not correct then that $H_i$ cannot be relative to non-separating cycle, but if it's from a separating non-contractible cycle $C$ then as $C$ separates the graph we obtain at least two subgraphs of $g\ge 1$.  
> **username_0**: Hi Saeed, thank you for your comment! I originally thought like what you commented above. But I do not know why Mohar did not included such an argument to his paper, that would be a stronger statement, and of course, that also depends on how you interpret the relative component $H_i$. I asked for an example because sometimes with topology, it is intuitively clear but making a full argument is non-trivial like Jordan Curve Theorem.  

---

## 0 answers

