planar graphs course homework 2
rootward computation
give a linear time algorithm for the following:
- input: a rooted tree
with vertex weights 
. - output: a table
subtree_weightgiving, for each vertex
, the total weight of vertices in the subtree of rooted at .
i assume the idea is that from [cite:@graph_klein_2024]:
the idea is to use recursion where each node returns the weight of the subtree that it is the root of to its parent, so that by the time we are at the parent all we need to do is grab the sum of its children without having to go deeper.
the idea is to use recursion where each node returns the weight of the subtree that it is the root of to its parent, so that by the time we are at the parent all we need to do is grab the sum of its children without having to go deeper.
this item extends the rootward computation concept from the previous problem. to solve it you will need to use the concepts of interdigitating trees, fundamental cycles and enclosure.
give a linear-time algorithm for the following:
give a linear-time algorithm for the following:
- input: a planar embedded graph
, and a rooted spanning tree of . - output: a table giving, for each nontree edge
, the lowest common ancestor of 
and in .
by the definition of a fundamental cycle, for every nontree edge we have a corresponding fundamental cycle in , every such cycle without the edge is a subtree whose root is some node 
, if we can reproduce these cycles in linear time we can assign to each pair of nodes in the subtree the designated ancestor (which can also be done in linear time). we know only one such satisfactory subtree (and hence one ) exists because is a spanning tree which has to be acyclic and cannot contain 2 different paths between any 2 nodes.
first we number the spanning tree nodes by their levels, giving them a rank in the tree, this can be done using bfs starting at the given root of the tree, the nodes on the same level of the tree should get the same number and the deeper we go the higher the number is, this is demonstrated in [[blk:fig-planar-graphs-homework-1]].
to construct the cycles we can use the fact that
is a spanning tree of the faces of , where we have that each face, except one, is accompanied by a non-tree edge of , and each one of those faces defines a common lowest ancestor for the vertices in the face, so we would simply iterate through the non-tree edges, find their corresponding simple cycles and within these cycles look for the vertex with the lowest level which we appoint as the the root of the subtree, then insert the proper solution into the "table of solutions", this is demonstrated in [[blk:fig-planar-graphs-homework-1]].
to iterate through the cycles we apply a rootward routine to the interdigitating tree
that starts at the vertex 
whose degree is highest in , at each vertex 
we check the reversals of the darts of of to get the vertices surrounding the face in and grab the vertex with the lowest level among those to be the highest ancestor for all of the vertices in the face, then at every higher vertex in we apply the same process but compare the level of ancestor we receive to the ancestors we received from the children of the vertex, and pick the one with the lowest level.
/home/mahmooz/brain/pen/1733387212.8736415.xopp
to get a better understanding of the concepts i also had to draw [[blk:fig-planar-graphs-homework-2]].
/home/mahmooz/brain/pen/1733339937.1868992.xopp
the end product is shown in fig-planar-graphs-homework-3.
we have a corresponding fundamental cycle in , every such cycle without the edge is a subtree whose root is some node , if we can reproduce these cycles in linear time we can assign to each pair of nodes in the subtree the designated ancestor (which can also be done in linear time). we know only one such satisfactory subtree (and hence one ) exists because is a spanning tree which has to be acyclic and cannot contain 2 different paths between any 2 nodes.
first we number the spanning tree nodes by their levels, giving them a rank in the tree, this can be done using bfs starting at the given root of the tree, the nodes on the same level of the tree should get the same number and the deeper we go the higher the number is, this is demonstrated in [[blk:fig-planar-graphs-homework-1]].
to construct the cycles we can use the fact that
is a spanning tree of the faces of , where we have that each face, except one, is accompanied by a non-tree edge of , and each one of those faces defines a common lowest ancestor for the vertices in the face, so we would simply iterate through the non-tree edges, find their corresponding simple cycles and within these cycles look for the vertex with the lowest level which we appoint as the the root of the subtree, then insert the proper solution into the "table of solutions", this is demonstrated in [[blk:fig-planar-graphs-homework-1]].
to iterate through the cycles we apply a rootward routine to the interdigitating tree
that starts at the vertex whose degree is highest in , at each vertex we check the reversals of the darts of of to get the vertices surrounding the face in and grab the vertex with the lowest level among those to be the highest ancestor for all of the vertices in the face, then at every higher vertex in we apply the same process but compare the level of ancestor we receive to the ancestors we received from the children of the vertex, and pick the one with the lowest level.
/home/mahmooz/brain/pen/1733387212.8736415.xopp
to get a better understanding of the concepts i also had to draw [[blk:fig-planar-graphs-homework-2]].
/home/mahmooz/brain/pen/1733339937.1868992.xopp
the end product is shown in fig-planar-graphs-homework-3.
there is a slight problem in fig-planar-graphs-homework-3, we should be iterating through all the darts of a vertex in the dual graph, not the darts restricted to the interdigitating tree.
part 2
in class we proved the fundamental cycle lemma for graphs with face weights, but then used a version of the lemma for graphs with edge weights. in this problem you will justify this version of the lemma. a weight assignment is
-proper if no element weighs more than times the total weight.
prove that there is a linear-time algorithm that, given a triangulated connected plane graph , a spanning tree of , and a 
-proper assignment of weights to faces, edges, and vertices, returns a nontree edge 
such that the fundamental cycle of with respect to is a 
-balanced cycle separator for .
, a spanning tree of , and a -proper assignment of weights to faces, edges, and vertices, returns a nontree edge such that the fundamental cycle of with respect to is a -balanced cycle separator for .by the fundamental cycle lemma, if we have a 
-proper assignment to faces then there is some whose fundamental cycle with respect to is a -balanced cycle separator, and since we have a triangulated graph, we have that each face has at most 3 vertices and 3 edges, giving us a total of 7 weight assignments for each face (3+3+1), each of which is 
, as a result we have that the total assignments for each face amount to 
, which equals 
, which gives us the satisfactory property to be able to invoke the fundamental cycle lemma, giving us the desired -balanced cycle separator.
-proper assignment to faces then there is some whose fundamental cycle with respect to is a -balanced cycle separator, and since we have a triangulated graph, we have that each face has at most 3 vertices and 3 edges, giving us a total of 7 weight assignments for each face (3+3+1), each of which is , as a result we have that the total assignments for each face amount to , which equals , which gives us the satisfactory property to be able to invoke the fundamental cycle lemma, giving us the desired -balanced cycle separator.prove the same as item (a), but when the weight assignment is 1/4-proper. hint: add artificial edges and faces with appropriate weights.
the idea is to offload the weights from vertices and edges onto faces, so that we can simply use the previous lemma to show that the desired separator must exist.
since the graph is triangulated, there are 3 possible cases for a face:
/home/mahmooz/brain/pen/1734291461.626836.xopp
we then invoke the fundamental cycle lemma on the modified graph to get that we have a-balanced cycle separator for the graph, this works because by modifying the faces in this matter we arent severely modifying the structure or changing other properties of the graph, and so it almost remains the same except for a few redundant edges.
since the graph is triangulated, there are 3 possible cases for a face:
- a face of size 1 (a self-loop) would receive 3 weight assigments, one for the face, one for the edge, and another for the vertex. we can turn it into a vertex with three non-intersecting self-loops, and offload the three assignment to the three faces.
- a face with two edges, it would have 5 weight assignments in total, we add 4 non-intersecting darts from one vertex to another to turn divide the face into 5 smaller faces that each get a
assignment. - a face with three edges and 7 weight assignments, we apply the same process with 6 new darts to divide the face into 7 smaller faces.
/home/mahmooz/brain/pen/1734291461.626836.xopp
we then invoke the fundamental cycle lemma on the modified graph to get that we have a
-balanced cycle separator for the graph, this works because by modifying the faces in this matter we arent severely modifying the structure or changing other properties of the graph, and so it almost remains the same except for a few redundant edges.part 3
slack costs: the notion of slack costs will be useful in various algorithms in this course.
let be a directed graph with length assignment 
from the darts to the real numbers, such that the length of every cycle in with respect to is non-negative. let 
be an assignment from the vertices of to the real numbers. the slack cost (sometimes called slack length) of a dart 
is defined as 
.
let
be a directed graph with length assignment from the darts to the real numbers, such that the length of every cycle in with respect to is non-negative. let be an assignment from the vertices of to the real numbers. the slack cost (sometimes called slack length) of a dart is defined as .
- let be a vertex. let be a vector such that, for each vertex ,
is the -to- distance in w.r.t. the lengths . prove that, for every dart in , the slack cost 
is non-negative. - show that if
is a shortest -to- path w.r.t. lengths , then it is also a shortest -to- path w.r.t. slack costs 
. what is the difference between the length of w.r.t. and w.r.t. ? - let be a directed sparse graph with dart lengths (i.e.,
). use the claims from parts (a) and (b) to compute the distance between every pair of vertices in in 
time.
to understand the problem better i sketched a little and demonstrated the ideas on some concrete examples:
/home/mahmooz/brain/pen/2024-12-10-Note-18-46.xopp
if the dart is in a self-loop then it is trivially true: let be a self-loop on a vertex , we have 
and 
but 
cant be negative because forms its own cycle and we cant have negative cycles.
proof for the first claim:
/home/mahmooz/brain/pen/2024-12-10-Note-18-46.xopp
if the dart is in a self-loop then it is trivially true: let
be a self-loop on a vertex , we have and but cant be negative because forms its own cycle and we cant have negative cycles.
proof for the first claim:
let 
be the shortest path between the nodes and 
, we have 2 possibilities: either the shortest path from to 
is 
, or is some other distinct path. if the case is the former then we have
and so the property holds. if we have a distinct path for 
, let it be 
such that 
(such a path has to exist because we have no negative cycles), we have 
, which means that 
.
proof for the second claim:
be the shortest path between the nodes and , we have 2 possibilities: either the shortest path from to is , or is some other distinct path. if the case is the former then we have
and so the property holds. if we have a distinct path for , let it be such that (such a path has to exist because we have no negative cycles), we have , which means that .let 
be some (directed) path from the node to the node , the path will start from and never visit it again, because if there is a path from to that visits twice it means that there is negative cycle in the graph, it will also not visit except one time, where it ends, it will not visit any 
(for 
) twice for the same reason, so we have that the darts on the path from to have to be distinct.
for any path, we have
we have that 
, hence the slack cost of the path boils down to:
the expression [[blk:eq-planar-graphs-hw-2-1]] is minimal when we have the smallest 
, and this is true by definition when the path 
is the shortest between and . we have 
is constant for any because 
and the distance from to wouldnt change no matter what path we pick, similarly we have that 
is constant for any because 
, and so the expression's value is only affected by 
when varies, and since this expression is minimal when the path 
is minimal (with respect to ), we know 
is minimal when is minimal.
proof for the third claim:
be some (directed) path from the node to the node , the path will start from and never visit it again, because if there is a path from to that visits twice it means that there is negative cycle in the graph, it will also not visit except one time, where it ends, it will not visit any (for ) twice for the same reason, so we have that the darts on the path from to have to be distinct.
for any path
, we have
we have that , hence the slack cost of the path boils down to:
the expression [[blk:eq-planar-graphs-hw-2-1]] is minimal when we have the smallest , and this is true by definition when the path is the shortest between and . we have is constant for any because and the distance from to wouldnt change no matter what path we pick, similarly we have that is constant for any because , and so the expression's value is only affected by when varies, and since this expression is minimal when the path is minimal (with respect to ), we know is minimal when is minimal.since gives us a function of the weights (cost with respect to ) that maintains a minimal cost for the minimal paths and gives us positive weights, we can use 
as the weights when looking for minimal paths, so we invoke dijkstra's algorithm 
times (once for each vertex) with as the weights of the edges, since dijkstra finds the distances from one vertex to all others, this will give us the distances for all pairs of vertices. dijkstra runs in 
time, but since we have that 
(the sparsity property), we have that dijkstra runs in 
time, so the algorithm runs in a total time of 
gives us a function of the weights (cost with respect to ) that maintains a minimal cost for the minimal paths and gives us positive weights, we can use as the weights when looking for minimal paths, so we invoke dijkstra's algorithm times (once for each vertex) with as the weights of the edges, since dijkstra finds the distances from one vertex to all others, this will give us the distances for all pairs of vertices. dijkstra runs in time, but since we have that (the sparsity property), we have that dijkstra runs in time, so the algorithm runs in a total time of part 4 (bonus problem)
this problem is another example for the use of separators. let be a directed planar graph with real arc weights. a negative cycle in is a cycle whose arc weights sum to a negative number. consider a negative cycle in that has the minimum number of edges. let 
denote the number of edges on this cycle. using separators, give an 
-time algorithm for finding . only describe the algorithm and analyze its running time. there is no need for a formal proof of correctness. you will need to use the bellman-ford algorithm for computing a shortest-path tree from a given source vertex in a graph with real edge weights. recall that this algorithm works in phases, where each phase relaxes all the edges of the graph, and, at the end of the 
'th phase, the algorithm has correctly computed, for each vertex , the length of the shortest -to- path that uses at most edges.
i didnt solve this one, (tbh i barely tried..)
be a directed planar graph with real arc weights. a negative cycle in is a cycle whose arc weights sum to a negative number. consider a negative cycle in that has the minimum number of edges. let denote the number of edges on this cycle. using separators, give an -time algorithm for finding . only describe the algorithm and analyze its running time. there is no need for a formal proof of correctness. you will need to use the bellman-ford algorithm for computing a shortest-path tree from a given source vertex in a graph with real edge weights. recall that this algorithm works in phases, where each phase relaxes all the edges of the graph, and, at the end of the 'th phase, the algorithm has correctly computed, for each vertex , the length of the shortest -to- path that uses at most edges.