Planar Graphs · Theory Problems

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Advanced Problems.

  1. (20 points) Define the distance between triangles \(A_{1}A_{2}A_{3}\) and \(B_{1}B_{2}B_{3}\) as \(\min\{|A_{i}B_{j}|\}\) over all \(i,j\). Can five non-degenerate triangles be placed in the plane so that the distance between every pair equals the sum of the radii of their circumscribed circles?
    Hint:
    Construct a disk of radius \(R\) centered at each vertex of the triangle. What can you say about the union of these disks for a single triangle, and the intersection of these unions for different triangles?
  2. (20 points) In this and the following problems, we denote by \(E_{d}\) the set of all boundary and interior edges of the face \(d\). \(V_{d}\) is the boundary vertices of a face \(d\) And the boundary of a face \(d\) is the subgraph \(B(d)\) of the graph \(G\) with vertex set \(V_{d}\) and edge set \(E_{d}\).

    Let \(G\) be a connected plane graph with no loops. Prove that \(G\) is \(2\)-vertex connected if and only if the boundaries of its faces are simple cycles.

    Example of a \(2\)-vertex connected plane graph:

  3. (25 points) Let \(G\) be a \(3\)-connected planar graph. Prove that the set of boundaries of its faces coincides exactly with the set of its non-separating induced cycles.

    Example of a \(3\)-connected plane graph:

    Hint:
    Menger's Theorem might be useful.
  4. (15 points) On the left and right in the figure are plane embeddings of the same graph. However, these embeddings are different (non-isomorphic). Indeed, in the right embedding there exists a face whose boundary contains six vertices, whereas in the left embedding no such face exists.

    Formally it can be defined as follows. Let \(G\) and \(G'\) be two plane graphs, and let \(\varphi : V(G) \to V(G')\) be a bijection satisfying the following conditions.

    • \(xy \in E(G)\) if and only if \(\varphi(x)\varphi(y) \in E(G')\);

    • a set \(U \subseteq V(G)\) is the set of boundary vertices of some face of the graph \(G\) if and only if \[\varphi(U) = \{\varphi(x) : x \in U\}\] is the set of boundary vertices of some face of the graph \(G'\).

    Then \(\varphi\) is an isomorphism of the plane graphs \(G\) and \(G'\), and the plane graphs themselves are called isomorphic.

    Prove that any two plane embeddings of a \(3\)-connected graph \(G\) are isomorphic as plane graphs.