$latex i\hbar\frac{\partial}{\partial t}\left|\Psi(t)\right>=H\left|\Psi(t)\right> $
$latex a+x/4$
Given an edge-weighted graph $latex G$ with a set $latex \term$ of $latex k$ terminals, a \emph{mimicking network} is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph $latex G$ being either an arbitrary graph or coming from a specific graph class.
In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with $latex k$ terminals that require $latex 2^{k-2}$ edges in any mimicking network. This nearly matches an upper bound of $latex \Oh(k 2^{2k})$ of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the $latex \Oh(k^2)$ upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde~[JCSS 1998] and by Khan and Raghavendra~[IPL 2014].
In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with $k$ terminals that require $latex 2^{k-2}$ edges in any mimicking network. This nearly matches an upper bound of $latex \Oh(k 2^{2k})$ of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the $latex \Oh(k^2)$ upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde~[JCSS 1998] and by Khan and Raghavendra~[IPL 2014].