1
$\begingroup$

Based on MacLane's planarity criterion, planar graphs are exactly those that admit a 2-basis. Such basis can be easily obtained considering $|E| - |V| + 1$ of its faces. Denoting those basis as trivial bases, my question is: are there examples of non-trivial 2-basis of a 2-connected planar graph?

A non-trivial basis should contain at least one cycle surrounding at least two faces. I could neither find an example nor prove their inexistence.

Any help would be highly appreciated.

$\endgroup$
2
  • $\begingroup$ Do you require that the degree of all vertices is at least 3? I think there are counterexamples if you allow degree 2 vertices. $\endgroup$ – Peter Shor Sep 17 '20 at 17:30
  • $\begingroup$ Yes, the vertices may have degree 2 $\endgroup$ – Manuel Dubinsky Sep 18 '20 at 13:38
5
$\begingroup$

The cycles of a 2-basis (and the one leftover cycle formed from the symmetric difference of all these cycles) necessarily form the faces of a planar embedding of the graph. First, all edges of the graph belong to some cycle by 2-connectivity. Second, the edges appearing only once in the basis cycles must form a single cycle, else their subgraph would have multiple cycles not all of which could be represented by the basis. So adding the leftover cycle produces a set of cycles that cover every edge exactly twice. Third, one can form an embedding of the graph onto a topological surface by making a polygon for each cycle and gluing these polygons together. One can use 2-connectivity again to show that the surface is actually a manifold: if multiple patches of surface touched each other locally at a single vertex, one could find a cycle passing from one patch to another through that vertex which could not be represented by the basis, because any basis representation would produce evenly many edges into that vertex within each patch of surface. And fourth, every cycle in the graph must be a boundary of a subset of the surface (it is the boundary the union of the basis cycle polygons whose symmetric difference is the given surface cycle). But this can be true only of a topological sphere, so the embedding is planar.

However, a planar graph that is 2-connected but not 3-connected can have multiple embeddings and when it does, the cycles of any given 2-basis may not be faces of a different embedding. As an example, $K_{2,4}$ has three combinatorially-distinct embeddings, for the three ways of choosing which pairs of degree-two vertices are non-co-facial, and for any particular embedding it is possible to find a cycle basis using one or both of the two non-facial cycles. (The degree-two vertices of this example can be replaced by two triangles connected edge-to-edge to make an example where all degrees are greater than two.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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