<p>This doesn't seem to be possible, at least not without finding the right notion of "easy".</p>

<p>Consider a graph formed by taking a grid graph with $k$ rows and $l+1$ columns, and identifying the leftmost column of vertices with the rightmost column of vertices. Here, we have $n = kl$ vertices, and we're interested in $k \le l$. The graph is planar, and has treewidth at least $k$, as it has a $k\times k$ grid graph as a minor.</p>

<p>Additionally, a cyclic separator achieving constant $f$ in this graph seems to need $\Omega(l)$ vertices (where the constant depends on $f$). Imagine the graph drawn on a cylinder of circumference $l$ and height $k$, where the graph forms an equally spaced grid on the surface of the cylinder. Then if a cyclic separator has length less than $l$, it cannot "go around" the cylinder. Hence a cyclic separator gives a way to find a region in a $k\times l$ rectangle whose perimeter is the length of the separator, and whose area is at least a constant ($1-f$) fraction of the whole rectangle's area. I don't know the exact isoperimetric inequality for this, but it seems like such a region would need perimeter $\Omega(l)$ in order to have enough area and fit into the rectangle.</p>

<p>Thus we have a graph with treewidth $k$ and whose separators need to be of size $\Omega(l)$. Choosing parameters like $k = n^\epsilon$ and $l = n^{1-\epsilon}$, we thus see that a cyclic $(s,f)$-separator for constant $f$ needs to have $s = \Omega(n^{1-\epsilon})$, even for graphs with treewidth $n^\epsilon$.</p>

CC BY-SA 3.0
2016-11-30T21:08:42.683Z
2016-11-30T21:08:42.683Z
Andrew Morgan
<p>An $(s,f)$- balanced separator in a graph $G$ is a set $S$  of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is said to be a cycle-separator.</p>

<blockquote>
  <p><strong>Question</strong>: for which smallest value of $\frac{s}{\sqrt{n}}$ such that $f$ is a constant there exists (and one which can be found in
  polynomial time) an $(s,f)$-cycle separator for all biconnected
  planar graphs which are not "easy" - the notion of easiness being (for
  example) bounded tree-width. Probably the parameters $s,f$ will depend
  on the tree-width $w$ of the easy class.</p>
</blockquote>

<p>Notice that I do not care about $f$ as long as it is a constant but $s$
(as a fraction of $\sqrt{n}$) is crucial for me.</p>

<p><strong>Some background</strong>:
Lipton-Tarjan gave a $(c\sqrt{n},\frac{2}{3})$-balanced planar (vertex) separator for some constant $c$. Subsequently Miller gave a similar separator that is also a <strong>cycle</strong> but in <strong>triangulated</strong> planar graphs.</p>

<p>If we omit the triangulated condition (say replace it by $2$-vertex connected) there might not exist an $(O(\sqrt{n}),O(1))$-cycle separator - case in point being a cycle on $n$ vertices. We can choose to ignore such easy (e.g. all bounded tree-width) cases.</p>

CC BY-SA 3.0
2016-11-28T21:51:50.897Z
What's the desired behavior on the following family of graphs? For $k,l$ with $kl=n$ and $k \le l$, form a grid graph with $k$ rows and $l+1$ columns and then identify the left-most column with the right-most column. It's planar, the treewidth is around $k$, and it seems like any cyclic separator would need size $\Omega(l)$ to achieve constant $f$. So with say $k = n^\epsilon$, you get large treewidth, but still need a fairly large separator. Is there another sense in which such graphs are "easy"?
Andrew Morgan
CC BY-SA 3.0
2016-11-30T20:38:00.027Z
@AndrewMorgan Point well made. This is indeed a hard instance for a single cycle separator. But maybe if I allowed 2 cycle-separators or in general O(1) many cycles which separate the graph in a balanced way - then this would be taken care of. However,  that may lead us far afield and require a different technique for separator computation. In the meantime if you convert your comment to an impossibility answer I will mark it as the correct answer. Thanks!
SamiD
<reference-request><graph-theory><graph-algorithms><planar-graphs>
Shortest cycle separator for biconnected planar graphs
SamiD
# Shortest cycle separator for biconnected planar graphs

(Asked by: username_0 on 2016-11-28)

An $(s,f)$- balanced separator in a graph $G$ is a set $S$ of $s$ vertices removing which yields connected compoennts of size at most $f|V|$. If the vertices of $S$ form a cycle of length $s$, $S$ is said to be a cycle-separator.

> **Question**: for which smallest value of $\frac{s}{\sqrt{n}}$ such that $f$ is a constant there exists (and one which can be found in
> polynomial time) an $(s,f)$-cycle separator for all biconnected
> planar graphs which are not "easy" - the notion of easiness being (for
> example) bounded tree-width. Probably the parameters $s,f$ will depend
> on the tree-width $w$ of the easy class.

Notice that I do not care about $f$ as long as it is a constant but $s$
(as a fraction of $\sqrt{n}$) is crucial for me.

**Some background**:
Lipton-Tarjan gave a $(c\sqrt{n},\frac{2}{3})$-balanced planar (vertex) separator for some constant $c$. Subsequently Miller gave a similar separator that is also a **cycle** but in **triangulated** planar graphs.

If we omit the triangulated condition (say replace it by $2$-vertex connected) there might not exist an $(O(\sqrt{n}),O(1))$-cycle separator - case in point being a cycle on $n$ vertices. We can choose to ignore such easy (e.g. all bounded tree-width) cases.

**Tags:** reference-request, graph-theory, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: What's the desired behavior on the following family of graphs? For $k,l$ with $kl=n$ and $k \le l$, form a grid graph with $k$ rows and $l+1$ columns and then identify the left-most column with the right-most column. It's planar, the treewidth is around $k$, and it seems like any cyclic separator would need size $\Omega(l)$ to achieve constant $f$. So with say $k = n^\epsilon$, you get large treewidth, but still need a fairly large separator. Is there another sense in which such graphs are "easy"?  
> **username_0**: @AndrewMorgan Point well made. This is indeed a hard instance for a single cycle separator. But maybe if I allowed 2 cycle-separators or in general O(1) many cycles which separate the graph in a balanced way - then this would be taken care of. However,  that may lead us far afield and require a different technique for separator computation. In the meantime if you convert your comment to an impossibility answer I will mark it as the correct answer. Thanks!  

---

## 1 answers

### Answer by username_1 on 2016-11-30. Score: 2 | Accepted answer

This doesn't seem to be possible, at least not without finding the right notion of "easy".

Consider a graph formed by taking a grid graph with $k$ rows and $l+1$ columns, and identifying the leftmost column of vertices with the rightmost column of vertices. Here, we have $n = kl$ vertices, and we're interested in $k \le l$. The graph is planar, and has treewidth at least $k$, as it has a $k\times k$ grid graph as a minor.

Additionally, a cyclic separator achieving constant $f$ in this graph seems to need $\Omega(l)$ vertices (where the constant depends on $f$). Imagine the graph drawn on a cylinder of circumference $l$ and height $k$, where the graph forms an equally spaced grid on the surface of the cylinder. Then if a cyclic separator has length less than $l$, it cannot "go around" the cylinder. Hence a cyclic separator gives a way to find a region in a $k\times l$ rectangle whose perimeter is the length of the separator, and whose area is at least a constant ($1-f$) fraction of the whole rectangle's area. I don't know the exact isoperimetric inequality for this, but it seems like such a region would need perimeter $\Omega(l)$ in order to have enough area and fit into the rectangle.

Thus we have a graph with treewidth $k$ and whose separators need to be of size $\Omega(l)$. Choosing parameters like $k = n^\epsilon$ and $l = n^{1-\epsilon}$, we thus see that a cyclic $(s,f)$-separator for constant $f$ needs to have $s = \Omega(n^{1-\epsilon})$, even for graphs with treewidth $n^\epsilon$.


---

