division into regions

a region $\text{[math]}$ of $\text{[math]}$ is an edge-induced subgraph of $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 definition 5.9.1]

a division of $\text{[math]}$ is a collection of regions such that each edge is in atleast one region. a vertex is a boundary vertex of the division if it is in more than one region. a division is an $r$-division if there are $\text{[math]}$ regions, and each region has at most $\text{[math]}$ vertices and $\text{[math]}$ boundary vertices.
[cite:;taken from @graph_klein_2024 definition 5.9.2]

a natural face of a region $\text{[math]}$ is a face of $\text{[math]}$ that is also a face of $\text{[math]}$ . a hole of $\text{[math]}$ is a face of $\text{[math]}$ that is not natural.
[cite:;taken from @graph_klein_2024 definition 5.9.3]

an $\text{[math]}$ -division with few holes is an $\text{[math]}$ -division in which

any edge of two regions is on a hole of each of them, and
every region has $\text{[math]}$ holes.

[cite:;taken from @graph_klein_2024 definition 5.9.4]

a decomposition tree for $\text{[math]}$ is a rooted tree in which each leaf is assigned a region of $\text{[math]}$ such that each edge of $\text{[math]}$ is represented in some region. for each node $\text{[math]}$ of the decomposition tree, the region $\text{[math]}$ corresponding to $\text{[math]}$ is the subgraph of $\text{[math]}$ that is the union of the regions assigned to descendants of $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 definition 5.9.5]

a decomposition tree $\text{[math]}$ admits an $\text{[math]}$ -division with few holes if there is a set $\text{[math]}$ of nodes of $\text{[math]}$ whose corresponding regions form an $\text{[math]}$ -division of $\text{[math]}$ with few holes.
[cite:;taken from @graph_klein_2024 definition 5.9.6]

for a constant $\text{[math]}$ , there is an $\text{[math]}$ -time algorithm that, for any triangulated planar embedded graph $\text{[math]}$ , outputs a binary decomposition tree $\text{[math]}$ for $\text{[math]}$ that simultaneously admits an $\text{[math]}$ -division of $\text{[math]}$ with few holes for every $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 theorem 5.10.1]

since the input graph $\text{[math]}$ is assumed to be triangulated, it follows that, for every region $\text{[math]}$ of $\text{[math]}$ , every natural face is a triangle. the algorithm is invoked by calling the procedure $\text{[math]}$ , given in [cite:@graph_klein_2024 Algorithm 5.1].
given a connected region $\text{[math]}$ with more than $\text{[math]}$ edges, and given a recursion-depth parameter $\text{[math]}$ , $\text{[math]}$ first triangulates each hole of $\text{[math]}$ by adding an artificial vertex and attaching it via artificial edges to each occurrence of a vertex on the boundary of the hole. let $\text{[math]}$ be the resulting graph. the vertices and edges that are not artificial are natural.
next, the procedure uses the planar-cycle-separator algorithm to find a simple-cycle separator $\text{[math]}$ consisting of at most $\text{[math]}$ natural vertices, where $\text{[math]}$ is a constant and $\text{[math]}$ is the number of vertices of $\text{[math]}$ (which is equivalent to the number of natural vertices of $\text{[math]}$ ). depending on the current recursion depth $\text{[math]}$ , the cycle separates $\text{[math]}$ in a balanced way with respect to either vertices, boundary vertices, or holes.
note that the cycle separator algorithm is invoked on $\text{[math]}$ , which has more than $\text{[math]}$ vertices since it also has some artificial vertices. however, its shown in [cite:@graph_klein_2024 lemma 5.10.4] that there are at most twelve artificial vertices, the bound of $\text{[math]}$ still holds for some choice of $\text{[math]}$ (since $\text{[math]}$ ). the number of artificial vertices on the separator does not matter in the analysis of $\text{[math]}$ .
the cycle $\text{[math]}$ determines a bipartition of the faces of the triangulated graph $\text{[math]}$ , which in turn induces a bipartition $\text{[math]}$ of the natural faces of $\text{[math]}$ . for $\text{[math]}$ , let $\text{[math]}$ be the region consisting of the edges bounding the faces in $\text{[math]}$ , together with the edges of $\text{[math]}$ that are in $\text{[math]}$ (i.e., omitting the artificial edges added to triangulate the artificial faces).

If $\text{[math]}$ is connected then $\text{[math]}$ is connected and $\text{[math]}$ is connected.
[cite:;taken from @graph_klein_2024 lemma 5.10.2]

the procedure calls itself recursively on $\text{[math]}$ and $\text{[math]}$ , obtaining decomposition trees $\text{[math]}$ and $\text{[math]}$ , respectively. the procedure creates a new decomposition tree $\text{[math]}$ by creating a new root corresponding to the region $\text{[math]}$ and assigning as its children the roots of $\text{[math]}$ and $\text{[math]}$ .
[cite:;taken from @graph_klein_2024 lemma 5.10.2]

it is shown in [cite:@graph_klein_2024 chapter 5.10.1 number of holes] how to take care of holes.

let $\text{[math]}$ be the number of vertices in the original input graph $\text{[math]}$ . consider the decomposition tree $\text{[math]}$ of $\text{[math]}$ produced by $\text{[math]}$ . each node $\text{[math]}$ corresponds to a region $\text{[math]}$ . we define $\text{[math]}$ , and $\text{[math]}$ to be the number of boundary vertices of $\text{[math]}$ . we will show that for any given $\text{[math]}$ , $\text{[math]}$ admits an $\text{[math]}$ -division of $\text{[math]}$ . the analysis consists of two phases. in the first phase ([cite:@graph_klein_2024 lemma 5.10.8]), we identify a set of $\text{[math]}$ regions for which the number of vertices is at most $\text{[math]}$ , and the average number of boundary vertices is $\text{[math]}$ . however, some of the individual regions in this set might have too many boundary vertices (since the number of vertices and boundary vertices do not necessarily decrease at the same rate). we show that each such region can be replaced with smaller regions in $\text{[math]}$ so that every region has $\text{[math]}$ boundary vertices, and the total number of regions remains $\text{[math]}$ ([cite:@graph_klein_2024 lemma 5.10.9]).
[cite:@graph_klein_2024 chapter 5.10.3 number of holes]

[cite:;taken from @graph_klein_2024 chapter 5.10 computing a decomposition tree]