1
$\begingroup$

Suppose we have a cubic planar bipartite graph with no double edges. I am looking for a statement about the minimal distance between the square faces (shortest path from a vertex on the first square face to a vertex on another one). Are there any upper bounds?

$\endgroup$

1 Answer 1

4
$\begingroup$

In an $n$-vertex graph the squares can all be $\Omega(\sqrt n)$ steps away from each other, and this is tight.

E.g., start with an octahedron, subdivide each triangular face of it into a regular mesh of $d^2$ triangles (six edges meeting at every vertex, including the ones along the edges of the octahedron), and take the dual graph of the resulting subdivided polyhedron. It will have six squares, at the corners of the octahedron, separated by $\Theta(d)$ hexagons.

Conversely if you have a square that is $d$ steps away from any other square then the concentric layers of faces around it must have a number of faces that grows linearly with their distance from the square, so the number of faces in these layers is $\Omega(d^2)$. In order for the total number of faces to be $O(n)$, as it is in a planar graph, the minimum distance between two different squares must be $O(\sqrt n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.