planar graphs course homework 3

submission for:

eden asta 209147487
mahmood sheikh 212835466

in class we sketched how to solve the maximum matching problem in planar graphs using separators. we argued that the running time for any input graph $\text{[math]}$ is bounded by the
recurrence:
$\text{[math]}$ where $\text{[math]}$ is the number of vertices of $\text{[math]}$ and $\text{[math]}$ and $\text{[math]}$ are the number of vertices of the two parts of $\text{[math]}$ obtained by deleting the vertices of the separator. prove that $\text{[math]}$ . hint: use induction on $\text{[math]}$ . beware of using the big-oh notation too liberally...

we include the definition of $\text{[math]}$ :

if $\text{[math]}$ are two functions from $\text{[math]}$ to $\text{[math]}$ , then we

say that $\text{[math]}$ if there exists a constant $\text{[math]}$ such that $\text{[math]}$ for every sufficiently large $\text{[math]}$ ,
say that $\text{[math]}$ if $\text{[math]}$ ,
say that $\text{[math]}$ if $\text{[math]}$ and $\text{[math]}$ ,
say that $\text{[math]}$ if for every $\text{[math]}$ for every sufficiently large $\text{[math]}$ , and
say that $\text{[math]}$ if $\text{[math]}$ .

[cite:;taken from @computability_arora_2009 definition 0.2 (Big-Oh notation)]

we apply strong induction on $\text{[math]}$ , for the base step, consider $\text{[math]}$ or $\text{[math]}$ , the problem can be solved in constant time (no need to apply a divide-and-conquer approach because there's nothing to divide), we have $\text{[math]}$ trivially. assume for the induction hypothesis that for every $\text{[math]}$ we have $\text{[math]}$ (for some constant $\text{[math]}$ ), we apply the induction step:
$\text{[math]}$ which gives us the constant $\text{[math]}$ for which we have $\text{[math]}$ for any sufficiently large $\text{[math]}$ and this means $\text{[math]}$ by definition.

in class we mentioned that there are data structures that can support all the necessary operations for MSSP in $\text{[math]}$ time per operation. in this problem you will develop a simpler data structure that supports similar operations on sequences (i.e., on paths) instead of on trees. this will give you a feeling for how the data structure for trees may be constructed.
we shall represent a sequence of numbers $\text{[math]}$ by storing the numbers in a balanced binary search tree, where element $\text{[math]}$ is considered less (in the tree order) than element $\text{[math]}$ if $\text{[math]}$ .

describe how to support the operations $\text{[math]}$ , which splits the sequence immediately after the $\text{[math]}$ 'th element, and $\text{[math]}$ which, given two sequences $\text{[math]}$ with a total of $\text{[math]}$ elements, returns a single sequence consisting of all the elements of $\text{[math]}$ followed by all the elements of $\text{[math]}$ . the running time should be $\text{[math]}$ , where $\text{[math]}$ is the total number of elements. you may use the standard BST operations split and join (make sure you understand how they are implemented in at least one specific balanced BST implementation, but you do not have to explain that in your answer). make sure to address the following issue: you cannot afford to store the index of each element explicitly since the indices of many elements are changed by the join operation.
describe how to also support in $\text{[math]}$ time the operation $\text{[math]}$ , which returns the $\text{[math]}$ 'th number in the sequence, and the operation $\text{[math]}$ , which, adds $\text{[math]}$ to the first $\text{[math]}$ elements of the sequence.
describe how to also support in $\text{[math]}$ time the operation $\text{[math]}$ , which reverses the order of the elements between indices $\text{[math]}$ and $\text{[math]}$ in the sequence.
(bonus 5 points) describe how to also support the operation $\text{[math]}$ , which returns the minimum number among the first $\text{[math]}$ elements in the sequence.

using AVL trees we can concatenate two trees in $\text{[math]}$ , search is also $\text{[math]}$ , which can be used to split a given sequence.
let $\text{[math]}$ denote the BSTs corresponding to the sequences $\text{[math]}$ , respectively.
to implement $\text{[math]}$ we consider the following: the elements of $\text{[math]}$ should be placed before the elements of $\text{[math]}$ in the tree, so that for any $\text{[math]}$ , we have that $\text{[math]}$ in the tree, and more generally we need to have that $\text{[math]}$ according to the order of the tree, to accomplish this we "stitch" the two trees $\text{[math]}$ together in such a way that rebalancing the resulting tree isnt too expensive.
note that the keys in $\text{[math]}$ arent the values themselves but rather the indicies, each node holds both an index and a value (among other potential metadata), for example the node corresponding to $\text{[math]}$ will have the value of $\text{[math]}$ , but its key in the tree will be the index $\text{[math]}$ , which means that the tree will be ordered according to the indicies of the sequence, but not necessarily the values, this allows us to place arbitrary values in the sequence but maintain the order that we like.
the steps for $\text{[math]}$ are:

remove the rightmost node from $\text{[math]}$ as you would in any AVL tree (this node would have the biggest key in $\text{[math]}$ , due to the ordering property of AVL trees),
construct a new tree with the left child being the modified tree $\text{[math]}$ , and the right child being the tree $\text{[math]}$ ,
apply AVL rotations to $\text{[math]}$ as necessary as if we just inserted it into the tree.

we may have to apply $\text{[math]}$ rotations to the new root to get the tree to be balanced, this would still take $\text{[math]}$ time. this algorithm runs in $\text{[math]}$ . an example is demonstrated in [[blk:fig-planar-graphs-homework-3-1]].
/home/mahmooz/brain/pen/2024-12-23-Note-22-35.xopp
to implement $\text{[math]}$ , we search for $\text{[math]}$ ( $\text{[math]}$ refers to the node whose key is $\text{[math]}$ ) as we would in a binary search tree, which takes $\text{[math]}$ , and while looking for $\text{[math]}$ , we store the first node that has an index bigger than $\text{[math]}$ that we encounter, call it $\text{[math]}$ , once we reach $\text{[math]}$ , we extract the subtree rooted at $\text{[math]}$ and apply a left rotation to $\text{[math]}$ to get its right child to become the parent of the subtree that was rooted at $\text{[math]}$ , then remove the left subtree that is now rooted at the node whose index was $\text{[math]}$ , this is demonstrated in [[blk:fig-planar-graphs-homework-3-2]]. note that if we store the path we took to get from $\text{[math]}$ to $\text{[math]}$ during the search, splitting the tree would be a matter of pointer manipulation and would take constant time.
/home/mahmooz/brain/pen/1735029847.303587.xopp
to implement $\text{[math]}$ we apply the same search routine and grab the element with key $\text{[math]}$ and return its value.
to support $\text{[math]}$ we use $\text{[math]}$ to first identify the set of nodes that we need to operate on, but we cant apply the operation directly because that would take time that is linear in $\text{[math]}$ , we instead use a technique called lazy propagation.
we place a special mark we call "to-add" (using node "metadata") on the root of the first split of the tree, and other marks named "dont-add" on the nodes where we make the green cuts shown in [[blk:fig-planar-graphs-homework-3-2]], the first mark will hold the value $\text{[math]}$ which will tell us that all values of the nodes of the subtree rooted at the marked node need to be increased by $\text{[math]}$ ( $\text{[math]}$ can be equal to $\text{[math]}$ or can be an accumulation of $\text{[math]}$ for subsequent calls to $\text{[math]}$ ). the latter marks called "dont-add" will tell us that the effect of the first mark ends at those nodes, so that we dont apply add $\text{[math]}$ to the entire subtree unnecessarily. this wont modify the values of the nodes directly, but rather would be handled upon a call to one of the functions $\text{[math]}$ or any other function that applies a search routine to the tree, the function that applies the seaerch routine needs to check if the node it visits are descendants of a marked node, and apply the addition if so, then it needs to propagate the mark to its children, unless one of them has the "dont-add" mark that stops the "to-add" mark of its parent.
to support $\text{[math]}$ we use the same idea of lazy propagation where we mark nodes for reversal instead of for adding a constant $\text{[math]}$ , to apply the reversal we would rotate the positions of the children of a node that we visit, so that the right child becomes the left child, and the left child becomes the right child (we apply this operation whenever we visit a node that is marked for reversal during later traversal of the tree).

let $\text{[math]}$ be an $\text{[math]}$ -vertex planar graph with non-negative dart lengths. let $\text{[math]}$ and $\text{[math]}$ be two faces, and $\text{[math]}$ be a simple path from a vertex on $\text{[math]}$ to a vertex on $\text{[math]}$ . give an $\text{[math]}$ -time algorithm that returns a minimum length simple cycle that enclosess exactly one of $\text{[math]}$ and $\text{[math]}$ , and crosses $\text{[math]}$ at most once. you probably understand intuitively what is meant by saying a path $\text{[math]}$ crosses $\text{[math]}$ . here is a formal definition: we say dart $\text{[math]}$ enters a simple path $\text{[math]}$ from the left if $\text{[math]}$ is an internal vertex of $\text{[math]}$ , and if the orbit of $\text{[math]}$ induces the cycle $\text{[math]}$ , where $\text{[math]}$ is the dart of $\text{[math]}$ whose head is $\text{[math]}$ , and $\text{[math]}$ is the dart of $\text{[math]}$ whose tail is $\text{[math]}$ . $\text{[math]}$ enters $\text{[math]}$ from the right if the induced cycle is $\text{[math]}$ . we say dart $\text{[math]}$ emanates left (right) of a simple path $\text{[math]}$ if $\text{[math]}$ enters $\text{[math]}$ from the left (right). we say a path $\text{[math]}$ crosses $\text{[math]}$ if there is a subpath of $\text{[math]}$ that can be written as $\text{[math]}$ , where $\text{[math]}$ enters $\text{[math]}$ from the left (right), $\text{[math]}$ is a (possibly empty) subpath of $\text{[math]}$ , and $\text{[math]}$ emanates right (left) of $\text{[math]}$ . hints: this problem is related to MSSP. the following thought experiment is useful. think of the graph $\text{[math]}$ embedded on a piece of paper. what becomes of the path $\text{[math]}$ when you take a knife, make an incision along $\text{[math]}$ , and then pull apart both sides of the incision? You may assume that the representation of the primal tree $\text{[math]}$ at any time along the execution of the MSSP algorithm allows you to query the length of the path in $\text{[math]}$ from the root to any vertex $\text{[math]}$ in $\text{[math]}$ time.
let $\text{[math]}$ be an undirected connected planar graph with non-negative edge lengths. let $\text{[math]}$ and $\text{[math]}$ be two faces of $\text{[math]}$ . give an $\text{[math]}$ -time algorithm that finds the shortest cycle in $\text{[math]}$ that separates $\text{[math]}$ and $\text{[math]}$ .
for vertices $\text{[math]}$ , $\text{[math]}$ in an undirected graph with edge capacities, a minimum st-cut is a set of edges that separates $\text{[math]}$ and $\text{[math]}$ and whose sum of capacities is minimum. let $\text{[math]}$ , $\text{[math]}$ be two distinct vertices in an undirected connected planar graph $\text{[math]}$ with non-negative edge capacities. give an $\text{[math]}$ -time algorithm that returns a minimum st-cut in $\text{[math]}$ .

\includepdf[pages=-]{homemahmooz/brain/notes/data/1f/fe88a0-709c-4a44-a00e-6e7cfdb3b016/eden.pdf}