# Shortest cycle separator for biconnected planar graphs

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.

• 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"? Commented Nov 28, 2016 at 21:51
• @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! Commented Nov 30, 2016 at 20:38

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$.