graph separator

if $\text{[math]}$ and $\text{[math]}$ are such that every $\text{[math]}$ path in $\text{[math]}$ contains a vertex or an edge from $\text{[math]}$ , we say that $\text{[math]}$ separates the sets $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ . we say that $\text{[math]}$ separates two vertices, $\text{[math]}$ if it separates the sets, $\text{[math]}$ , but $\text{[math]}$ , and that $\text{[math]}$ separates $\text{[math]}$ if $\text{[math]}$ separates some two vertices in $\text{[math]}$ . a separating set of vertices is a separator, we may also call a single vertex $\text{[math]}$ a separator if the set $\text{[math]}$ is a separator.
[cite:;taken from @graph_diestel_2017 chapter 1.4 connectivity]

a vertex $\text{[math]}$ is a separation vertex in an undirected graph $\text{[math]}$ iff there exist two vertices $\text{[math]}$ such that every path between $\text{[math]}$ and $\text{[math]}$ goes through $\text{[math]}$ .

let $\text{[math]}$ be a planar embedding, and let $\text{[math]}$ be a number between 0 and 1. an assignment of nonnegative weights to the faces, vertices, or edges of $\text{[math]}$ is an $\text{[math]}$ -proper assignment if no element is assigned more than $\text{[math]}$ times the total weight. a subpartition of these elements is $\text{[math]}$ -balanced if, for each part, the sum of the weights of the elements of that part is at most $\text{[math]}$ times the total weight.
[cite:;taken from @graph_klein_2024 chapter 5.2 weights and balance]

let $\text{[math]}$ be binary tree, and let $\text{[math]}$ be a $\text{[math]}$ -proper assignment of weights to nodes such that each nonleaf node is assigned at most one-fourth of the weight. there is an edge $\text{[math]}$ such that every tree in $\text{[math]}$ has at most three-fourths of the weight.
[cite:;taken from @graph_klein_2024 lemma 1.3.2 tree edge separator of node weight]

assume the total weight is 1. for each node $\text{[math]}$ , define
$\text{[math]}$ let $\text{[math]}$ be a leafmost 3/4-heavy node with respect to $\text{[math]}$ . let $\text{[math]}$ be the children of $\text{[math]}$ . note that $\text{[math]}$ because its a binary tree. since $\text{[math]}$ but $\text{[math]}$ , we must have $\text{[math]}$ , so $\text{[math]}$ (because nonleaf nodes get at most one-fourth of the weight).
for $\text{[math]}$ , let $\text{[math]}$ be the weight of descendants of $\text{[math]}$ . let $\text{[math]}$ . by choice of $\text{[math]}$ , $\text{[math]}$ . by choice of $\text{[math]}$ ,
$\text{[math]}$ this shows that choosing $\text{[math]}$ to be the edge $\text{[math]}$ satisfies the balance condition.
[cite:;taken from @graph_klein_2024 lemma 1.3.2]

let $\text{[math]}$ be a plane graph. a simple cycle $\text{[math]}$ of $\text{[math]}$ defines a subpartition consisting of two parts, the strict interior and the strict exterior of the cycle. if the subpartition is $\text{[math]}$ -balanced, we say that $\text{[math]}$ is an $\text{[math]}$ -balanced cycle separator.
[cite:;taken from @graph_klein_2024 chapter 5.3 fundamental-cycle separators]

for any plane graph $\text{[math]}$ , $\text{[math]}$ -proper assignment of weights to faces, and spanning tree $\text{[math]}$ of $\text{[math]}$ such that the boundary of each face of $\text{[math]}$ has at most three nontree edges, there is a nontree edge $\text{[math]}$ such that the fundamental cycle of $\text{[math]}$ with respect to $\text{[math]}$ is a $\text{[math]}$ -balanced cycle separator for $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 5.3.1]

let $\text{[math]}$ be the interdigitating tree, the spanning tree of $\text{[math]}$ consisting of edges not in $\text{[math]}$ . the vertices of $\text{[math]}$ are faces of $\text{[math]}$ , and are therefore assigned weights. the property of $\text{[math]}$ ensures that $\text{[math]}$ has degree at most three. using lem-graph-sep-2, let $\text{[math]}$ be an edge separator in $\text{[math]}$ of vertex weight. by the fundamental-cut and fundamental cycle duality, the fundamental cut of $\text{[math]}$ in $\text{[math]}$ with respect to $\text{[math]}$ is a simple cut in $\text{[math]}$ (each side of which has weight at most three-fourths of the total) so it is, by the simple-cycle/simple-cut theorem, a simple cycle in $\text{[math]}$ that encloses between one-fourth and three-fourths of the weight.
[cite:;taken from @graph_klein_2024 lemma 5.3.1]

there is a linear-time algorithm that, given a triangulated plane graph $\text{[math]}$ , a spanning tree $\text{[math]}$ of $\text{[math]}$ , and a $\text{[math]}$ -proper assignment of weights to faces, edges, and vertices, returns a non-tree edge $\text{[math]}$ such that the fundamental cycle of $\text{[math]}$ with respect to $\text{[math]}$ is a $\text{[math]}$ -balanced cycle separator for $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 5.3.2]

we can give a better balance guarantee if we separating just edge-weight:

there is a linear-time algorithm that, given a triangulated plane graph $\text{[math]}$ with a $\text{[math]}$ -proper assignment of weights to edges, and a spanning tree $\text{[math]}$ , returns a nontree edge $\text{[math]}$ such that the fundamental cycle of $\text{[math]}$ with respect to $\text{[math]}$ is a $\text{[math]}$ -balanced cycle separator for $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 5.3.3]

separators are extremely useful for divide-and-conquer algorithms. in order to ensure that we dont place too much weight on a single subgraph, we need to make sure that the separator we choose is balanced and isnt too big, this motivates the following theorems.

there is a linear-time algorithm that, for a plane graph $\text{[math]}$ and $\text{[math]}$ -proper assignment of weights to edges, returns subgraphs $\text{[math]}$ such that

$\text{[math]}$ is a [[blk:def-partition][partition]] of $\text{[math]}$ (but is it really a partition? because $\text{[math]}$ ),
the partition $\text{[math]}$ is $\text{[math]}$ -balanced, and
$\text{[math]}$ .

the subgraphs $\text{[math]}$ are called the pieces. the set $\text{[math]}$ of vertices common to the two subgraphs is called the vertex separator.
[cite:;taken from @graph_klein_2024 theorem 5.5.1]

let $\text{[math]}$ denote the edge-weight assignment. assume for notational simplicity that the sum of edge weights is 1. the basic idea is to find a balanced fundamental-cycle separator, which might be too long, and shortcut it at small BFS levels.
the algorithm adds artificial zero-weight edges to $\text{[math]}$ to triangulate it. then, it performs a breadth-first search of $\text{[math]}$ from some node $\text{[math]}$ . let $\text{[math]}$ be the breadth-first-search tree. let $\text{[math]}$ denote the set of vertices at level $\text{[math]}$ . following lem-graph-sep-3, the algorithm finds a $\text{[math]}$ -balanced fundamental-cycle separator $\text{[math]}$ with respect to $\text{[math]}$ . we partition the edges of $\text{[math]}$ into two sets $\text{[math]}$ and $\text{[math]}$ , so that $\text{[math]}$ contains all edges strictly enclosed by $\text{[math]}$ and $\text{[math]}$ contains all edges not enclosed by $\text{[math]}$ . the edges of $\text{[math]}$ are assigned to $\text{[math]}$ and $\text{[math]}$ in a way that makes the partition $\text{[math]}$ -balanced. such a partition exists because the weight assignment $\text{[math]}$ is $\text{[math]}$ -proper, and can be computed in linear time by assigning the edges of $\text{[math]}$ to $\text{[math]}$ until the total weight of $\text{[math]}$ is at least $\text{[math]}$ .
let $\text{[math]}$ and $\text{[math]}$ denote the minimum and maximum level of a vertex of $\text{[math]}$ , respectively. for an integer $\text{[math]}$ , let $\text{[math]}$ denote $\text{[math]}$ , and let $\text{[math]}$ denote $\text{[math]}$ . let $\text{[math]}$ be the greatest integer satisfying:

$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ .

if no such level exists, we set $\text{[math]}$ . let $\text{[math]}$ be the smallest integer satisfying:

$\text{[math]}$ ,
$\text{[math]}$ ,
$\text{[math]}$ .

if no such level exists, we set $\text{[math]}$ .
since for any level $\text{[math]}$ , the sets of edges corresponding to $\text{[math]}$ and to $\text{[math]}$ are disjoint, at least one of $\text{[math]}$ , $\text{[math]}$ is true. it follows that each of the levels $\text{[math]}$ has greater than $\text{[math]}$ vertices. hence, the total number of vertices among these levels is greater than $\text{[math]}$ , so $\text{[math]}$ .
let $\text{[math]}$ be the set of edges whose endpoints have level at most $\text{[math]}$ if $\text{[math]}$ , and the empty set if $\text{[math]}$ . let $\text{[math]}$ be the set of edges with at least one endpoint at level greater than $\text{[math]}$ if $\text{[math]}$ , and the empty set if $\text{[math]}$ . let $\text{[math]}$ , and let $\text{[math]}$ .
it is immediate to verify that $\text{[math]}$ is a partition of the edges of $\text{[math]}$ . by choice of $\text{[math]}$ and $\text{[math]}$ , for $\text{[math]}$ we have $\text{[math]}$ . since $\text{[math]}$ is a balanced separator, for $\text{[math]}$ we have $\text{[math]}$ .
for $\text{[math]}$ , if $\text{[math]}$ , then the algorithm sets $\text{[math]}$ and $\text{[math]}$ all other edges of $\text{[math]}$ . since $\text{[math]}$ , it follows that $\text{[math]}$ and $\text{[math]}$ .
assume therefore that $\text{[math]}$ for $\text{[math]}$ . let $\text{[math]}$ be the minimum integer such that $\text{[math]}$ . then $\text{[math]}$ and $\text{[math]}$ , so $\text{[math]}$ . the algorithm sets $\text{[math]}$ and $\text{[math]}$ all other edges of $\text{[math]}$ . then $\text{[math]}$ and $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 theorem 5.5.1]

there is a linear-time algorithm that, for a plane graph $\text{[math]}$ and $\text{[math]}$ -proper assignment of weights to vertices, returns subgraphs $\text{[math]}$ such that

$\text{[math]}$ is a partition of $\text{[math]}$ ,
the subpartition $\text{[math]}$ of $\text{[math]}$ is $\text{[math]}$ -balanced, and
$\text{[math]}$ .

[cite:;taken from @graph_klein_2024 theorem 5.5.2]

we sometimes may want a simple cycle separator, which the-graph-sep-1 doesnt guarantee (fundamental cycle doesnt guarantee a simple cycle separator, see [[blk:fig-fund-cut-cycle]]), the following theorem addresses this:

there is a linear-time algorithm that, for any simple undirected triangulated plane graph and any $\text{[math]}$ -proper assignment of weights to faces, edges, and vertices, returns a $\text{[math]}$ -balanced cycle separator $\text{[math]}$ of size at most $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 theorem 5.8.1]