A*, Randomized algos

Question 1

What is planar graph? How is called a drawing of a planar graph?

Answer 1

Planar graph is a graph, which can be drawn in the plane in a way s.t. no two edges intersect geometrically (except at the vertex to which both are incident). Such drawing is called planar embedding

Question 2

What are Kuratowski graphs?

Answer 2

Cannot be drawn in a plane without crossing edges. i.e. K3,3 or K5

Question 3

How many edges and vertices are there for simple planar graphs and for simple planar bipartite graphs?

Answer 3

for |V| >= 3, |E| <= 3|V| - 6

for bipartite: if |V| >= 3 then |E| <= 2|V| - 4

Question 4

Define Wagner’s theorem

Answer 4

A graph is planar iff it has no minor isomorphi to K5 or K3,3