Geometry combinatorics and algorithms
Prüfungsfragen
Prüfungsfragen
How can one construct an arrangement of lines in R2? Describe the incremental algorithm and prove that its time complexity is quadratic in the number of lines (incl. statement and proof of the Zone Theorem).
Graph in DCEL: insert new line li: start on left of bounding box: find leftmost face, that intersects l. Split face and update everything accordingly. add a vertex at intersection with the next line, continue in that fashion until rightmost face is reached.
Only faces that intersect li are relevant. So called zone: set of cells that intersect li. Thm: there are <10n lines in all cells of L. proof. Assume li is horizontal (else rotate everything) We only consider left bounding faces and show <5n: consider the rightmost intersection point p, where r in L intersects something. R is rightmost cell of L without r. We want to consider what happens, when inserting r: It intersects R at most at 2 points, splitting 2 left bound edges and maybe being left bounding itself. So by induction 5(n-1)+3<5n leftbounding edges. If multiple edges intersect at the same point p, they can additionally split rs edges, so we get 5 new leftbound edges.
How can one test whether there are three collinear points in a set of n given points in R2? Describe an O(n2) time algorithm.
Dualize: (a,b) is a line y:ax-b 3 points are colinear iff the 3 corr. lines intersect. (compute intersection of two lines and store in a hash table, if already there, return true, else false)
How can one compute the minimum area triangle spanned by three out of n given points in R2? Describe an O(n2) time algorithm.
fix two points pq. Then equivalent to finding r closest to line through p and q. Dualize: find closest point l* to p* intersect q* that has the same x-coord and lies on some r*. Then r is the solution. Do this for every pair, incrementally update when inserting new lines then no additional costs.
What is a ham sandwich cut? Does it always exist? How to compute it? State and prove the theorem about the existence of a ham sandwich cut in R2 and describe an O(n2) algorithm to compute it and sketch the O(n log n) algorithm by Edelsbrunner and Waupotitsch.
Line splitting two distinct sets at the same time, such that each side of the line has half of each set. Always exists. proof (and O(n^2) algo): Dualize the points. Then consider the median-level line of both (consisits of line segments and all slopes are distinct so they intersect in at least one point) This point corresponds to a line seperating both sets. O(nlogn): recursive algo, input: (L1,L2,k1,k2,(x1,x2)) With two sets of lines, two k-levels and interval. take mu at line with median slope, seperate plane into 4 quarter by line parallel to mu and one line x=j where j ist the median x-coordinate of all intersection points. If j is in the interval, we can update the interval to (x1,j) or (j,x2) and also dircard one quater of the lines, where the intersection points lie in the resp quater (We pair a big slope with a small slope line)
What is the endpoint visibility graph for a set of disjoint line segments in the plane and how can it be constructed? Give the definition and explain the relation to shortest paths. Describe the O(n2) algorithm by Welzl, including a proof of Theorem 9.14.
Given n disjoint line segments, we connect p and q if they are on the same segment or if pq intersect with the whole set is {p,q} (they see each other)
Constructing: Sweep from vertically down to vertically up.We only need to consider directions parallel to some pq . for p store s(p) segment p sees. if slope of pq is parallel to current direction an s(p) =pq add edge pg. If q is obscured by s(p) no change, if q endpoint of s(p) add pq and s(p):=s(q) if q is endpoint of s that now obscures s(p) change s(p) to s and add pq. We have n^2 events and need sorting thus n^2 log n, to get rid of logn: pq has larger slope than pr iff p* intersect q* has greater x coord than p* intersect r*, can be sorted in linear time usng breast first search
Is there a subquadratic algorithm for General Position? Explain the term 3-Sum hard and its implications and give the reduction from 3-Sum to General Position.
No subquadratic algo, it is known, that quadratic time is required for 3-sum problem. General position: No 3 points colinear: Is equivalent to: are there three points such that their sum is 0? : lift all points tp (p,p^3) 3 of them a,a^3 b,b^3 c,c^3 are colinear iff slope through any pair (a,b),(b,c) is the same iff a+b+c=0
Which problems are known to be 3-Sum-hard? List at least three problems (other than 3-Sum) and briefly sketch the corresponding reductions.
colinearity, minimum area triangle (gen. of general position), GeomBase: given points on lines y=0,y=1,y=2 is there a line passing through 3 of them? 3 sum with distinct points
Algo: sort numbers, i=1,..n j=i+1,k=n, j++ if <0 k++ if >0
What is an (n,s) Davenport-Schinzel sequence and how does it relate to the lower envelope of real-valued continuous functions? Give the precise definitions and some examples. Explain in particular how to apply the machinery to line segments.
sequence of alphabet with n elements, such that so s+2 alternating subsequence. every such sequence can be modeled by lower envelope sequence for n continuous functions. If these functions are line segments, we have 0 in the sequence if no segment is defined here.
What is the value of λs(n), for 1 ⩽ s ⩽ 3? Derive the precise value for s ∈ {1, 2} and prove an O(n log n) upper bound for λ3(n).
1: no seqeunce aba (happens as soon as an element appears twice. 2nd 2n-1. 3: ababab: consider element with least appearances a: a...bab...a can not appear_> del as plus at most 2 more and apply indcution
What is the combinatorial complexity of the lower envelope of a set of n lines/parabolas/line segments?
lines can intersect at most once: n^2 changes. paraboles: one containes in another: 2 changes per pair of line. Line segments: endpoints (4) plus intersection =5
What is a face of a polytope? What is a vertex, an edge, a ridge, a facet?
Give precise definitions!
Face of polytope: Polytope intersected with supporting hyperplane (there is a hyperplane s.t. the face is in hyperplane and P in h+) , dim=k: k-face: vertices: o-faces, edges 1-faces facets: n-1-faces, ridges n-2-faces.
Can you characterize vertex-edge graphs of 3-dimensional polytopes? Explain Steinitz’ Theorem.
3 dim polytope iff 3-connected planar graph
What is a hypercube? What is a simplex? Define these polytope and explain what their faces are.
hypercube: -1<=xi<=1. vertices: some 1 some -1. Simplex convex hull of n affinely independent vertices. Faces: lower dimensional hypercubes/simplices
How many k-faces can a d-dimensional polytope with n vertices have? Prove a nontrivial upper bound.
n over k+1, since every face is a polytope itself.
How connected is the graph of a polytope? State and prove Balinski’s theorem.
d dimensional polytope is d connected. prove: fix some set S of size d-1 and fix some v0. Consider hyperplane through S and v0. Then points are either above ans thus connected to max face or below and connected to min face, v0 connects both, max/min faces are polytopes themselves, so by induction connected
How many facets can a 4-dimensional polytope with n vertices have? Prove a lower bound of Ω(n2).
consider 2 skew symmetric lines, perturb points on in slightly, then ever pair of two adjacent points of each line is delaauney and thus facet.
What is a regular triangulation? Give the definition and show that not all triangulations are regular.
Triangulation regular if it can be obtained by projecting the lower convex hull of a lifting of P to r d+1. Non-regular: 2 triangles in each other.
What is the secondary polytope? Describe the construction and explain its connection to the flip graph of regular triangulations.
secondary polytope: convex hull of GKZ vectors of all triangulations. vertices one to one to regular triangulations, edges are flips. so 1-skeleton is flip graph of regulat triangulations. a flip takes a triangulated convex d+2 dim subset of P and replaces it by unique other triangulation.
Let P ⊂ R2 be a set of n points in general position (with the origin).
What does sum_i=0^n−3 2^i h_i count?
number of embracing set (every embr. set contains triangle and points below)
Show that a simplicial d-dimensional polytope P with d + 2 vertices
has always k(d+2−k) facets, for some 2⩽k⩽d.
dualize: polytope in d+2-d-1=1 dimension: line. Then an embracing set (=facet in primal) is a set that contains a point from the left and one from the right of 0. Assume k points on the left. Then d+2-k on the right. k can not be one, sinceotherwise d+1 vertices are on one side and we thus have d+1 facets on d+2 points which is not possible.
Show that the union of countably many open sets in Rd is open. Show that the union of a finite number of closed sets in Rd is closed. (For the curious reader: These are two of the axioms of an abstract topology. So here we show that the Euclidean space is a topology.) What follows for intersections of open and closed sets? Finally, show that the union of countably many closed sets in Rd is not necessarily closed.
countable union open: \(x\in U=\bigcup_{a=1}^{\infty} \implies x\in U_a \implies \exists \varepsilon: B_{\varepsilon}(x)\subset U_a\subset U.\)
finite union closed: \(F^c=(\bigcup_{i=1}^nF_i)^c=\bigcap_{i=1}^nF_i^c\) by DeMorgan, but only works for finitely many.
finite intersections of open sets are open, countable intersections of closed sets are closed.
counterexample non-closed: \(\bigcup_{n=1}^{\infty}[\frac{1}{n},1]\)
Show that for any P ⊆ Rd the interior P◦ is open, and the closure
\(\bar{P}\) is closed. (Why is there something to show to begin with?)
interior: All points interior to P. let \(x\in P\) then by definition x is interior to P,i.e. \(\exists B_{\varepsilon}(x)\subset P.\)
closure: all points that are neither interior to P nor to \(\mathbb{R}^n\backslash P.\) Let \(x\in \mathbb{R}^n\backslash\bar{P}. \) Then is must be interior to Rn, since otherwise it would be in the boundary or in P.
Prove:
The average vertex degree in a simple planar graph is less than six.
average degree: \(\frac{2|E|}{n}\leq\frac{2(3n-6)}{n}\leq\frac{6n}{n}=6\) (All edges incident to two vertices, average= total/number of vertices)
Show that neither K5 (the complete graph on five vertices) nor K3,3 (the complete bipartite graph where both classes have three vertices) is planar.
K5: number of edges =10, but 3n-6=15-6=9 which is smaller than 10.
K3,3: n=6, e=9 and by euler f=5. Because bipartite, no triangles, hence every face must be bounded by at least 4 edges. and thus 4f<=3e
Let P be a set of n ⩾ 3 points in the plane such that the distance between every pair of points is at least one. Show that there are at most 3n − 6 pairs of points in P at distance exactly one.
Construct graph, s.t. \(uv\in E \iff d(u,v)=1\) then this is planar: if not, an edge ab crossed another edge cd but then some edge in {ac,ad,bc,bd} must have distance less than 1.
A graph is 1-planar if it admits a drawing in the plane in which every edge has at most one crossing. Prove or disprove: The family of 1-planar graphs is minor-closed.
Wrong. Consider some non 1 planar graph H (e.g. K7) and a plane embedding of it. Then there are edges with two crossings. For each such double-crossing, place a vertex in between the two crossings, and you will get a 1 planar graph that has H as a minor (by contracting one of the newly obtained edges)
(a) Give an example of a 6-connected planar graph or argue that no such graph exists.
(b) Give an example of a 5-connected planar graph or argue that no such graph exists.
(c) Give an example of a 3-connected outerplanar graph or argue that no such graph exists.
6-connected: \(deg(v)\geq6 \implies |E|\geq \frac{6n}{2}=3n, but |E|\leq 3n-6\).
5-connected: isocahedron
3-connected outerplanar (all vertices lie on outer face): There is at least one vertex of degree at most 2 which is a contradiction.
Why is the previous halfedge prev(·) stored explicitly whereas the source vertex of a halfedge is not in DCEL?
One can just go to twins target, the previous halfedge can be "far" away, if the face is large.
Give pseudocode to traverse all edges incident to a given vertex v of a DCEL.
\(s \gets \text{halfedge}(v)\\h \gets s\\\text{while }h\neq s:\\\text{do something with }h\\h\gets next(twin(h))\\\text{endwhile} \)
Give pseudocode for the operation join-face(h) in DCEL. Specify preconditions if needed.
\(\text{join-face}(h):\\h_2 \gets twin(h)\\\text{update al prev and next from } h \text{ and }h_2\\f\gets \text{new face}\text{loop starting at next(h) and set all faces to }f\)
Implement from scratch updating everything, or use other functions: (prob. slower...)
split-edge(h):
\(u \gets target(h)\\v\gets target(twin(h))\\w\gets \text{coordinates between u and v}\)
join-faces(h)
add-vertex-at(w,h)
split-face(edge coming into u,v)
Let G be a planar graph with vertex set {1, . . . , 9}. Try to find an embedding corresponding to the following list of circular sequences of faces:
(a) {(1,4,5,6,3),(1,3,6,2),(1,2,6,7,8,9,7,6,5),(7,9,8),(1,5,4)}
(b) {(1,4,5,6,3),(1,3,6,2),(1,2,6,7,8,9,7,6,5),(7,9,8),(1,4,5)}
a: draw the faces one after another, biggest one is outer face.
b: can not be planar, we have the sequence 1,4,5 appearing twice. (Would have to boarder two faces on the same side)
prove: Lemma 2.20. In a biconnected plane graph every face is bounded by a cycle.
and
Corollary 2.21. For any vertex v in a 3-connected plane graph, there is a cycle that contains all neighbors of v.
2.20: By definition a face is bounded by a closed walk. Now assume the closed walk is not a cycle. I.e. there exists some vertex v that is visited at least twice. But then the path from v to v lies entirely in F (By Jordan Curve theorem, considering the cycle, that "continues" when reaving v) and is only connected to F via v. Thus, revoming v from the graph would disconnect the graph and it would thus not be biconnected.
2.21. removing v leaves a bipartite graph and all faces v was incident to will be merged into one face and by the lemma there exists a cycle around these.
Describe a linear time algorithm that, given an abstract planar graph G and a cycle C in G, tests whether C is a facial cycle. (You may assume that planarity can be tested in linear time.)
This is equivalent to saying that G\C is connected.
test if G is planar and output a planar embedding.
G' = G\C
test if G' is connected (e.g. BFS starting on some vertex, counting how many vertices are reached)
Let G = (V,E) be a biconnected graph and let C be a collection of directed cycles of G. Assume that for every directed edge (u,v) whose underlying undirected edge {u, v} is in E, there is exactly one cycle C ∈ C that contains (u, v). Further assume that for every vertex v ∈ V, the deg(v) cycles in C that contain v can be ordered as C0,...,Cdeg(v)−1 such that for every pair u,v ∈ V and i ∈ N with (u,v),(v,w) ∈ Ci there exists an x ∈ V such that (w,v),(v,x) ∈ Ci+1 (where indices are taken modulo deg(v)). Prove or disprove: The collection C describes a combinatorial plane embedding of G.
True. Every edge used exactly once. Ordering at vertices is a rotational order, that makes sure everything is labelled counterclockwise and that you switch directions when revisiting a vertex.
Describe a family of biconnected planar graphs with exponentially many combinatorial plane embeddings. That is, show that there exists a constant c ∈ R such that for every n ∈ N there exists a biconnected planar graph on n vertices that has at least c^n different combinatorial plane embeddings.
Define a diamond: two endpoints u,v and 3 vertices in between: a,b,c and add edges u-a-v, u-b-v, u-c-v. This is biconnected and has 2 different combinatorial ambeddings.
Now, start with a cycle on k vertices and replace each edge by a diamont -> n=4k vertices and \(2^k=2^{\frac{n}{4}}=2^{\frac{1}{4}^n}\)possible combinatorial embeddings.
Prove: Theorem 2.31. A maximal planar graph on n ⩾ 4 vertices is 3-connected.
We know, that it is 2 connected and that every face is a triangle. So assume it is not 3 connected. I.e there is some cut set u,v. s.t. G\u,v=A u B disconnected. Since its 2-connected, both u and v must be connected to both A and B. But then there exists some face containing at least one vertex from A and B resp. and u and v, hence at least 4 vertices, which is a contradiction.
(a) A minimal nonplanar graph is a non-planar graph G which con- tains an edge e such that G \ e is planar. Prove or disprove: Every minimal nonplanar graph contain an edge e such that G \ e is maximal planar.
(b) A maximal-plus-one planar graph is a graph G that contains an edge e such that G \ e is maximal planar. Prove or disprove: Every maximal-plus-one planar graph can be drawn with at most one crossing.
a) Counterexample: Start with K5, subdivide one edge (add a new vertex v in the middle) this is minimal non.planar, but removing an edge does not result in maximal planar, argue with number of edges or just show: one can add an edge between x and other elements.
b)Counterexample: 3 stacked triangles, pick a vertex in the innermost and one in the outermost triangle and add that edge.
We discussed the DCEL structure to represent plane graphs in Sec- tion 2.2.1. An alternative way to represent an embedding of a maximal planar graph is the following: For each triangle, store pointers to its three vertices and to its three neighboring triangles. Compare both approaches. Discuss different sce- narios where you would prefer one over the other. In particular, analyze the space requirements of both.
Space of DCEL: O(n), but 32n (counting pointers per edge, vertex, face, and replacing |E| by 3n etc), heaviliy inflienced by number of edges
Space of other approach: 6|F|=6(2n)=12n
If maximal planar, probably latter more efficient, if we want arbitrary graph, first one
-
- 1 / 119
-
Flashcards
Show that the union of countably many open sets in Rd is open. Show that the union of a finite number of closed sets in Rd is closed. (For the curious reader: These are two of the axioms of an abstract topology. So here we show that the Euclidean space is a topology.) What follows for intersections of open and closed sets? Finally, show that the union of countably many closed sets in Rd is not necessarily closed.
countable union open: \(x\in U=\bigcup_{a=1}^{\infty} \implies x\in U_a \implies \exists \varepsilon: B_{\varepsilon}(x)\subset U_a\subset U.\)
finite union closed: \(F^c=(\bigcup_{i=1}^nF_i)^c=\bigcap_{i=1}^nF_i^c\) by DeMorgan, but only works for finitely many.
finite intersections of open sets are open, countable intersections of closed sets are closed.
counterexample non-closed: \(\bigcup_{n=1}^{\infty}[\frac{1}{n},1]\)
Show that for any P ⊆ Rd the interior P◦ is open, and the closure
\(\bar{P}\) is closed. (Why is there something to show to begin with?)
interior: All points interior to P. let \(x\in P\) then by definition x is interior to P,i.e. \(\exists B_{\varepsilon}(x)\subset P.\)
closure: all points that are neither interior to P nor to \(\mathbb{R}^n\backslash P.\) Let \(x\in \mathbb{R}^n\backslash\bar{P}. \) Then is must be interior to Rn, since otherwise it would be in the boundary or in P.
Prove:
The average vertex degree in a simple planar graph is less than six.
average degree: \(\frac{2|E|}{n}\leq\frac{2(3n-6)}{n}\leq\frac{6n}{n}=6\) (All edges incident to two vertices, average= total/number of vertices)
Show that neither K5 (the complete graph on five vertices) nor K3,3 (the complete bipartite graph where both classes have three vertices) is planar.
K5: number of edges =10, but 3n-6=15-6=9 which is smaller than 10.
K3,3: n=6, e=9 and by euler f=5. Because bipartite, no triangles, hence every face must be bounded by at least 4 edges. and thus 4f<=3e
Let P be a set of n ⩾ 3 points in the plane such that the distance between every pair of points is at least one. Show that there are at most 3n − 6 pairs of points in P at distance exactly one.
Construct graph, s.t. \(uv\in E \iff d(u,v)=1\) then this is planar: if not, an edge ab crossed another edge cd but then some edge in {ac,ad,bc,bd} must have distance less than 1.
A graph is 1-planar if it admits a drawing in the plane in which every edge has at most one crossing. Prove or disprove: The family of 1-planar graphs is minor-closed.
Wrong. Consider some non 1 planar graph H (e.g. K7) and a plane embedding of it. Then there are edges with two crossings. For each such double-crossing, place a vertex in between the two crossings, and you will get a 1 planar graph that has H as a minor (by contracting one of the newly obtained edges)
(a) Give an example of a 6-connected planar graph or argue that no such graph exists.
(b) Give an example of a 5-connected planar graph or argue that no such graph exists.
(c) Give an example of a 3-connected outerplanar graph or argue that no such graph exists.
6-connected: \(deg(v)\geq6 \implies |E|\geq \frac{6n}{2}=3n, but |E|\leq 3n-6\).
5-connected: isocahedron
3-connected outerplanar (all vertices lie on outer face): There is at least one vertex of degree at most 2 which is a contradiction.
Why is the previous halfedge prev(·) stored explicitly whereas the source vertex of a halfedge is not in DCEL?
One can just go to twins target, the previous halfedge can be "far" away, if the face is large.
Give pseudocode to traverse all edges incident to a given vertex v of a DCEL.
\(s \gets \text{halfedge}(v)\\h \gets s\\\text{while }h\neq s:\\\text{do something with }h\\h\gets next(twin(h))\\\text{endwhile} \)
Give pseudocode for the operation join-face(h) in DCEL. Specify preconditions if needed.
\(\text{join-face}(h):\\h_2 \gets twin(h)\\\text{update al prev and next from } h \text{ and }h_2\\f\gets \text{new face}\text{loop starting at next(h) and set all faces to }f\)
Implement from scratch updating everything, or use other functions: (prob. slower...)
split-edge(h):
\(u \gets target(h)\\v\gets target(twin(h))\\w\gets \text{coordinates between u and v}\)
join-faces(h)
add-vertex-at(w,h)
split-face(edge coming into u,v)
Let G be a planar graph with vertex set {1, . . . , 9}. Try to find an embedding corresponding to the following list of circular sequences of faces:
(a) {(1,4,5,6,3),(1,3,6,2),(1,2,6,7,8,9,7,6,5),(7,9,8),(1,5,4)}
(b) {(1,4,5,6,3),(1,3,6,2),(1,2,6,7,8,9,7,6,5),(7,9,8),(1,4,5)}
a: draw the faces one after another, biggest one is outer face.
b: can not be planar, we have the sequence 1,4,5 appearing twice. (Would have to boarder two faces on the same side)
prove: Lemma 2.20. In a biconnected plane graph every face is bounded by a cycle.
and
Corollary 2.21. For any vertex v in a 3-connected plane graph, there is a cycle that contains all neighbors of v.
2.20: By definition a face is bounded by a closed walk. Now assume the closed walk is not a cycle. I.e. there exists some vertex v that is visited at least twice. But then the path from v to v lies entirely in F (By Jordan Curve theorem, considering the cycle, that "continues" when reaving v) and is only connected to F via v. Thus, revoming v from the graph would disconnect the graph and it would thus not be biconnected.
2.21. removing v leaves a bipartite graph and all faces v was incident to will be merged into one face and by the lemma there exists a cycle around these.
Describe a linear time algorithm that, given an abstract planar graph G and a cycle C in G, tests whether C is a facial cycle. (You may assume that planarity can be tested in linear time.)
This is equivalent to saying that G\C is connected.
test if G is planar and output a planar embedding.
G' = G\C
test if G' is connected (e.g. BFS starting on some vertex, counting how many vertices are reached)
Let G = (V,E) be a biconnected graph and let C be a collection of directed cycles of G. Assume that for every directed edge (u,v) whose underlying undirected edge {u, v} is in E, there is exactly one cycle C ∈ C that contains (u, v). Further assume that for every vertex v ∈ V, the deg(v) cycles in C that contain v can be ordered as C0,...,Cdeg(v)−1 such that for every pair u,v ∈ V and i ∈ N with (u,v),(v,w) ∈ Ci there exists an x ∈ V such that (w,v),(v,x) ∈ Ci+1 (where indices are taken modulo deg(v)). Prove or disprove: The collection C describes a combinatorial plane embedding of G.
True. Every edge used exactly once. Ordering at vertices is a rotational order, that makes sure everything is labelled counterclockwise and that you switch directions when revisiting a vertex.
Describe a family of biconnected planar graphs with exponentially many combinatorial plane embeddings. That is, show that there exists a constant c ∈ R such that for every n ∈ N there exists a biconnected planar graph on n vertices that has at least c^n different combinatorial plane embeddings.
Define a diamond: two endpoints u,v and 3 vertices in between: a,b,c and add edges u-a-v, u-b-v, u-c-v. This is biconnected and has 2 different combinatorial ambeddings.
Now, start with a cycle on k vertices and replace each edge by a diamont -> n=4k vertices and \(2^k=2^{\frac{n}{4}}=2^{\frac{1}{4}^n}\)possible combinatorial embeddings.
Prove: Theorem 2.31. A maximal planar graph on n ⩾ 4 vertices is 3-connected.
We know, that it is 2 connected and that every face is a triangle. So assume it is not 3 connected. I.e there is some cut set u,v. s.t. G\u,v=A u B disconnected. Since its 2-connected, both u and v must be connected to both A and B. But then there exists some face containing at least one vertex from A and B resp. and u and v, hence at least 4 vertices, which is a contradiction.
(a) A minimal nonplanar graph is a non-planar graph G which con- tains an edge e such that G \ e is planar. Prove or disprove: Every minimal nonplanar graph contain an edge e such that G \ e is maximal planar.
(b) A maximal-plus-one planar graph is a graph G that contains an edge e such that G \ e is maximal planar. Prove or disprove: Every maximal-plus-one planar graph can be drawn with at most one crossing.
a) Counterexample: Start with K5, subdivide one edge (add a new vertex v in the middle) this is minimal non.planar, but removing an edge does not result in maximal planar, argue with number of edges or just show: one can add an edge between x and other elements.
b)Counterexample: 3 stacked triangles, pick a vertex in the innermost and one in the outermost triangle and add that edge.
We discussed the DCEL structure to represent plane graphs in Sec- tion 2.2.1. An alternative way to represent an embedding of a maximal planar graph is the following: For each triangle, store pointers to its three vertices and to its three neighboring triangles. Compare both approaches. Discuss different sce- narios where you would prefer one over the other. In particular, analyze the space requirements of both.
Space of DCEL: O(n), but 32n (counting pointers per edge, vertex, face, and replacing |E| by 3n etc), heaviliy inflienced by number of edges
Space of other approach: 6|F|=6(2n)=12n
If maximal planar, probably latter more efficient, if we want arbitrary graph, first one
Give a 4-connected nonplanar graph that does not contain a subdivision of K5.
\(K_{4,4}\) (subdivision: obtain one graph from another by subdividing its edges)
Every 5-connected nonplanar graph contains a subdivision of K5.
Show the following:
(a) For every natural number n ⩾ 4, there exist a planar graph G on n vertices and a set P ⊂ R2 of n points in general position (no three points are collinear) so that G does not admit a plane straight-line embedding on P.
(b) For every natural number n ⩾ 6, there exist a planar graph G on n vertices and a set P ⊂ R2 of n points in general position (no three points are collinear) so that (1) G does not admit a plane straight-line embedding on P; and (2) there are three points in P forming a triangle that contains all other points from P.
a) Pick point set that is on the convex hull of the point set (e.g. all on a circle) Then any edge must be drawn inside the convex hull. Then e.g. for vertices aligned on the circle in the order v1,..,vk the graph containing the edges vi,vi+1 and vi,vi+2 does not admit a straight line embedding.
b) consider some graph G that does not admit a straight line embedding on n>=4 vertices (as in a) Now consider a vertex v that is "outside" (there is a hyperplane separating the point from all others) and add two more points that together with this vertex make up a triangle. This exists, since we can move the points arbitrarily far away and we can find an angle with the separating hyperplane not equal to 0. It is planar, since we can find a planar embedding of G where v is on the outer face.
Show that for every set P ⊂ R2 of n ⩾ 3 in general position (no three points are collinear) the cycle on n vertices admits a plane straight-line embedding on P.
Take convex hull. Connect them in the order arising from a rotation in one direction around some (e.g.middle) point in the convex hull, if a point lies strictly inside, insert it, where it appears in the rotation.
(a) Compute a canonical ordering for the following internally trian- gulated plane graphs:
(b) Design an infinite family of internally triangulated plane graphs on 2k vertices with at least k! canonical orderings.
(c) Design an infinite family of internally triangulated plane graphs, along with specific choices for v1,v2, so that each graph in the family has a unique canonical ordering starting from v1,v2.
a) fix v1,v2, then start from the back (end of permutation) and make sure everything fulfills 3 axioms
b) ?
c) Start with a triangle v1,v2,v3, in every step add a new vertex vi and connect it to v1,v2,vi-1, such that the new outer face is v1v2vi.
(a) Describe a plane graph G with n vertices that can be embedded (while preserving the outer face) in straight-line on a grid of size (2n/3) × (2n/3), but not on a smaller grid.
(b) Can you draw G on a smaller grid if you are allowed to change the outer face?
?
Prove: Theorem 2.50 (Schnyder [30]). For every maximal planar graph G on at least three vertices and every fixed face f of G, the multigraph obtained from G by doubling the (three) edges of f can be partitioned into three spanning trees.
Hint: Fix a canonical ordering; for every vertex vk take the edge to its first neighbor on C◦(Gk−1); argue that the edges form a spanning tree.
Fix f as the outer face and fix a canonical ordering. First spanning tree as described in the hint plus one copy of v1v2. Is a spanning tree: every vertex (except v1) is connected to exactly one lower vertex and thus no cycles can form and since it always connects to existing structure it is connected. Other two spanning trees: choose last and middle vertex along C°(Gk-1)
What is an embedding? What is a planar/plane graph? Give the definitions and explain the difference between planar and plane.
An embedding of a graph G is a drawing of a graph in the euclidean space \(\mathbb{R}^2\) where each vertex is a point and each edge is a curve. and The endpoints of the edges are the vertices, no edge crosses another vertex and the map from vertices to points in R2 is injective. A planar graph is a graph that has a plane embedding (But also has non-planar embeddings!) A plane embedding is an embedding, where no two edges cross.
How many edges can a planar graph have? What is the average vertex degree in a planar graph? Explain Euler’s formula and derive your answers from it.
Eulers Formula:in a connected, planar graph: |V|-|E|+|F|=2. (proof by induction on |E|-|V|)
Every face is bounded by at least 3 edges and every edge bounds 2 faces. 3|F|<=2|E| plugging in above formula for |F| yields |E|<=3|V|-6
Average vertex degree in planar graph is less or equal to 6. av vertex degree:\(\frac{2|E|}{|V|}\leq \frac{2(3|V|-6)}{|V|}\leq 6\)
How can plane graphs be represented on a computer? Explain the DCEL data structure and how to work with it.
DCEL: every edge is directed halfedge, halfedge is stored with pointers to prev, next, target, twin, face, face is anticlockwise cycle, pointer to arbitrary halfedge within, vertex stores coordinates and pointer to arbitrary halfedge originating there. storange O(n)
Easy operations: insert vertex within a face, split face, join two faces (update stuff accordingly)
How can a given plane graph be (topologically) triangulated efficiently? Explain what it is, including the difference between topological and geometric trian- gulation. Give a linear time algorithm, for instance, as in Theorem 2.34.
topological triangulation: augmentation to maximal planar graph (every face is a triangle).
geometric triangulation: Straight-line embedding, where no further straight lines can be added. (every bounded face is triangle)
Algo: proof of 3.34 (add triangle to cut vertices and then add stars/bistars in every face starting at vertex that face points to)
What is a combinatorial embedding? When are two combinatorial embeddings equivalent? Which graphs have a unique combinatorial plane embedding? Give the definitions, explain and prove Whitney’s Theorem.
Combinatorial embedding: list of faces (counterclockwise path), equivalent if the same or globally reversed.
Whitney: Any 3-connected planar graph has a unique combinatorial embedding.
Proof: Assume there exists two different ones. Then there is some C bounding face is only one. Then case 1) C(bounding face) had a chord vw. Split C into both sides of the chord A,B. then by 3-connectivity there is some path P A-B not using endpoints of the chord. Let a/b be the last/first element in A/B. Then we can add some vertex v inside the face C bounds and connect it to a,b,v,w, but then K5 is a minor.
case2) C is induced but seperating: G\C=AuB disconnected by Menger thm for \(a\in A, b\in B\) there are 3 internally disjoint paths between a and b. add a vertex to each of these paths Now add another vertex v inside the face C bounds and connect to to the previous points. Then K3,3 is a minor.
What is a canonical ordering and which graphs admit such an ordering? For a given graph, how can one find a canonical ordering efficiently? Give the definition. State and prove Theorem 2.46.
canonical ordering: permutation of the vertices of G s.t. for all k=3,..,n: Gk is internally triangulated, \(v_1,v_2\in C_°(Gk)\)(outer cycle) and vk is located in the outer face of Gk-1. Every maximal planar graph admits such an ordering,
Thm: For every internally triangulated plane graph G and every edge v1v2 on its outer cycle, there exists a canonical ordering for G that starts with v1,v2. Moreover, such an ordering can be computed in linear time.
Proof: induction. n=3 all are valid. Then find a vertex \(v_n\in C_°(G)\backslash\{v_1,v_2\} s.t.G_{n-1}:=G\backslash v_n\) is internally triangulated. For this, first show there exists such a vn that is not incident to a chord. If no chords are present, we are done, else pick the shortest chord and a point between its endpoints. Now show that Gn-1 is internally triangulated. every boundary face of Gn-1 is boundary face of G and thus triangle. Remains to show 2-connectivity: boundary in Gn-1 is boundary of G minus vn, plus all its "inner" neighbors. We can add vertex v in outer face and connect it to all vertices in outer face, then max-planar and this 3-connected, so when removing it, the graph stays 2-connected. For the algo per vertex store what outer face is it in? and the number of incident chords on the current outer cycle. See actual proof for full algo.
Which graphs admit a plane embedding using straight line edges? Can one bound the size of the coordinates in such a representation? State and prove Theorem 2.43.
Thm: Every planar graph on n ⩾ 3 vertices has a plane straight-line drawing on a (2n−3)×(n−1) integer grid. In fact, it can be computed in O(n) time.
Proof: Shift algorithm
Consider two edges e and f in a topological plane drawing so that e and f cross at least twice. Prove or disprove: There always exist two distinct crossings p and q of e and f so that the portion of e between p and q is not crossed by f, and the portion of f between p and q is not crossed by e.
True. For a counterexample we would need that the crossings are both permutations, but no two elements are neighboring in both permutations. But this would lead to self-intersections. (Still needs an argument)
Let G be a graph with n ⩾ 3 vertices, e edges, and cr(G) = e − (3n − 6). Show that in every drawing of G with cr(G) crossings, every edge is crossed at most once.
Assume that there is some edge f that is crossed at least twice. But then deleting f and one edge for every crossing where f is not involved, would give a plane graph. But we deleted at most cr(G)-1 edges (since f removed two crossings) but then \(e \leq (3n-6)+cr(G)-1\iff cr(G)\geq e-(3n-6)+1 \) a contradiction to the assumption.
Consider the abstract graph G that is obtained as follows: Start from a plane embedding of the 3-dimensional cube, and add in every face a pair of (crossing) diagonals. Show that \(cr(G) = 6 < \bar{cr}(G).\)
n=8, e=12+12=24. A plane graph on 8 vertices can have at most 3(8)-6=18 edges, so we need to remove 6 edges. This is a lower bound, an upper bound can be shown by an example embedding: draw the "front-side" of the cube as a square and the back side as a bigger square around it. Now connect the corresponding vertices. Now for each facet, add the diagonals, they will cross in every face. (This requires 2 edges in outer face that are not straight)
In straight-line embedding, we can not have one of the facets of the cube as an outer face. This results in additional crossings.
A graph is 1-planar if it can be drawn in the plane so that every edge is crossed at most once. Show that a 1-planar graph G on n ⩾ 3 vertices has at most 4n−8 edges and cr(G)⩽n−2.
Since it is 1-planar, to obtain a plane graph, we must remove exactly one edge per crossing. thus e=3n-6+cr(G).
Consider the graph with one edge removed per face and assume it is maximal planar (this is the maximal case). Then adding back an edge leads to 2 faces being split. (No more than two, because otherwise a line would be crossed multiple times) But every face can be split at most once, since two if its incident edges were crossed already and in order to split it, one must cross two of the incident edges, but only one is left, since its maximal planar. So at most |F|/2 edges can\(|E|\leq 3n-6+\frac{2n-4}{2}=4n-8\) be added to the 3n-6 ones from the maximal planar one. Thus
What is the crossing number of a graph? What is the rectilinear crossing number? Give the definitions and examples. Explain the difference.
crossing number: cr(G) is the minimal number of edges that cross in a drawing of G. Rectilinear crossing number: \(\bar{cr}(G)\) is the same in a straight-line drawing. examples: K5, K33: 1
Why is it called “Crossing Lemma” rather than “Crossing Theorem”? Explain at least two applications of the Crossing Lemma, for instance, your pick out of the Theorems 3.10, 3.11, and 3.13.
Lemma because it is mainly used in many other proofs.
Theorem 3.10 (Szemerédi-Trotter [14]). The maximum number of incidences between n points and m lines in R2 is at most\( 2^{5/3} ·n^{2/3}m^{2/3} +4n+m.\)
proof: P set of n points, L set of l lines, each cont. at least one point define G with V=P, vw edge iff v and w appear consecutive on some line. Naturally induced straight line embedding. Number of crossings \(\leq \binom{m}{2}\). Point on \(l=I_l\geq 1\), contributes \(I_l-1\)edges to G. \(|E|=\sum_{l\in L}(I_l-1)=I-m\) if |E| <=4 then \(I\leq 4n+m\). Else use crossing lemma: \(\binom{m}{2}\geq cr(G)\geq\frac{|E|^3}{64n^2}=\frac{(I-m)^3}{64n^2} \iff \frac{m^2-m}{2}\geq \frac{(I-m)^3}{64n^2} \implies (32m^2n^2)^{\frac{1}{3}}\geq I-m \iff 2^{5\frac{1}{3}}n^{\frac{2}{3}}m^{\frac{2}{3}}+m \geq I\) (is asymtotically tight)
Theorem 3.11. The maximum number of unit distances between n points in R2 is at most 5n4/3.
proof. P n points, C unit circles centered at P. number if incidences of C and P =2 number of unit distances. Define G: for c circle, list \(P\cap c\) in a circular fashion and add an edge between two adjacent vertices, unless loops or double edges. Contributes at least \(I_c-2\)edges. \(|E|\geq I-2n\). Now remove double edges that arose from two different circles: \(|E'|\geq |E|/2 \implies I\leq 2(|E'|+n)\). if \(|E'|\leq 4n \implies I\leq10n < 10n^{4/3}.\) Otherwise crossing lemma:\(n^2>2\binom{n}{2}\geq cr(G')\geq \frac{|E'|^3}{64n^2}\) (every pair of circles can intersect at most twice) then \(|E'|<4n^{4/3} \implies I<8n^{4/3}+2n<10n^{4/3}.\)
Theorem 3.13 (Elekes [6]). For A ⊂ R with |A| = n ⩾ 3 we have \(max \{|A+A|,|A·A|\}⩾ \frac{1}{4}n^{\frac{5}{4}}\) .
4
For a nonplanar graph, the more edges it has, the more crossings we would expect. Can you quantify such a correspondence more precisely? State and prove Lemma 3.2 and Theorem 3.7 (The Crossing Lemma).
Lemma 3.2. For a graph G with n ⩾ 3 vertices and e edges, we have cr(G) ⩾ e−(3n−6)
proof. for each crossing remove one edge then the graph is planar, we picked at most cr(G) edges (could be that line crosses at 2 points)
Theorem 3.7 (Crossing Lemma [4]). For a graph G with n vertices and e ⩾ 4n edges, we have \(cr(G)\geq \frac{e^3}{64n^2}\).
prrof cinsider minimal crossing and pick each vertex with probability p=4n/e for a subset U. N:=#sel. vertices, E[N]=np, M=#edges in G[U], E[M]=p^2e (both vertices have to be picked) C=#crossings in "same" drawing og G[U], E[C]=p^4cr(G) (adjacent edges dont cross, and thus 4 vertices have to be picked) Then \(C\geq cr(G[U])\geq M-3N\) by above lemma, so\(E[C]\geq E[M]-3E[N] \iff cr(G)\geq \frac{e}{p^2}-3\frac{n}{p^3}=\frac{e^3}{64n^2}\)
