Yes, a cycle basis of minimum total length is necessarily made up of induced cycles.
Let $\mathcal C_1,\mathcal C_2,\cdots, \mathcal C_r$ be a cycle basis of minimum total length, where $r\ge1$.
For the sake of contradiction, suppose $\mathcal C_1=(v_1,v_2,\cdots,v_q)$ where $v_1=v_q$ is not an induced cycle. That means $q\ge4$ and there is a "chord" $(v_a, v_b)$ across $\mathcal C_1$, i.e., $(v_a,v_b)$ is an edge of the original graph where $a,b$ are not adjacent integers nor $\{1, q-1\}$. WLOG, let the chord be $(v_1, v_p)$, where $v_p$ is not one of $v_1, v_2, v_{q-1}$. We have $2\lt p\lt q-1$.
Consider cycle $\mathcal D=(v_1,v_2 \cdots, v_p, v_1)$ and cycle $\mathcal E=(v_1, v_p, v_{p+1}, \cdots, v_q)$. Either $\mathcal D$ or $\mathcal E$ is not a $\mathbb Z_2$-combination of $\mathcal C_2, \cdots, \mathcal C_r$; otherwise, $\mathcal D + \mathcal E=\mathcal C_1$ is also a $\mathbb Z_2$-combination of them, which implies $\mathcal C_1,\mathcal C_2,\cdots, \mathcal C_r$ is not a cycle basis, which contradicts with our assumption.
WLOG, suppose $\mathcal D$ is not a $\mathbb Z_2$-combination of $\mathcal C_2, \cdots, \mathcal C_r$. That means $\mathcal D, \mathcal C_2, \cdots, \mathcal C_r$ are $\mathbb Z_2$-linearly independent. Hence $\mathcal D, \mathcal C_2, \cdots, \mathcal C_r$ is a cycle basis. However, its total length is less than that of $\mathcal C_1,\mathcal C_2,\cdots, \mathcal C_r$ since the length of $\mathcal D$ , $p$ is less than the length of $\mathcal C_1$, $q$. This is a contradiction.
To find a non-convex embedding of any planar quadrangulation $G$, induct on the number of vertices. We prove that for any plane embedding of $G$, there is a plane embedding with the same face structure where all faces have a concave angle. (The base case is the $4$-cycle, which we can embed as any concave quadrilateral.)
The general strategy is to find a low-degree vertex to remove. With $n$ vertices, there are $n-2$ faces and $2n-4$ edges, for an average degree of $4 - \frac8n$, so we can find a vertex $v$ of degree $3$ or less. There are two cases depending on $\deg(v)$:
- If $\deg(v)=2$ with neighbors $w_1, w_2$, then our plane embedding of $G$ gives us a plane embedding of $G-v$ (another quadrangulation!) where $w_1, w_2$ are opposite vertices on the same face. Find a non-convex embedding of $G-v$, then carefully put $v$ back.
- If $\deg(v)=3$ with neighbors $w_1, w_2, w_3$, then our plane embedding of $G$ gives us a plane embedding of $G-v$ where $w_1, w_2, w_3$ are three non-consecutive vertices of a face of length $6$. Add an edge $e$ from $w_1$ to its opposite vertex on that face to get a quadrangulation. Find a non-convex embedding of this graph ($G-v+e$), then remove the edge we added and carefully put $v$ back.
Let me elaborate on the "carefully put $v$ back" steps, with some drawings.
In the degree-$2$ case, the non-convex plane embedding of $G-v$ has a face with four vertices $x_1, x_2, x_3, x_4$, where $x_1$ and $x_3$ are supposed to be adjacent to $v$. There are seemingly many cases, depending on whether the face is an interior or exterior face, and depending on which of $x_1, x_2, x_3, x_4$ gives us the non-convex angle.
However, we don't need to do casework; all cases can be solved by putting $v$ back sufficiently close to vertex $x_2$. First of all, this guarantees that edges $x_1v$ and $x_3v$ can be drawn as straight line segments (because they're very close to the straight line segments $x_1x_2$ and $x_3x_2$). Second, the two faces we get are
- $x_1vx_3x_4$, which is non-convex because it's very close to the former face $x_1x_2x_3x_4$, and
- $x_1x_2x_3v$, which is non-convex because we can make $\angle x_2x_1v$ and $\angle x_2x_3v$ arbitrarily small, and once $\angle x_2x_1v + \angle x_2x_3v < |\angle x_1x_2x_3 - 180^\circ|$, we know that either $\angle x_1 x_2 x_3$ or $\angle x_1 v x_3$ must exceed $180^\circ$.
In the degree-$3$ case, the non-convex embedding of $G-v+e$ has an embedding with two faces $x_1 x_2 x_3 x_4$ and $x_1 x_4 x_5 x_6$, where $e$ (the edge that doesn't exist in $G$) is $x_1 x_4$, and $v$ is supposed to be adjacent to $x_1, x_3, x_5$. Again, there are seemingly many cases for which face (if any) is an interior face, and which angles are concave. Here are a few:
However, once again, we can solve all the cases by placing $v$ sufficiently close to $x_4$. The three faces created are:
- $x_1 x_2 x_3 v$, which has a non-convex angle because it can be made arbitrarily close to the face $x_1 x_2 x_3 x_4$ in the non-convex embedding of $G-v+e$;
- $x_3 x_4 x_5 v$, which has a non-convex angle by the same argument as in the degree-$2$ case ($\angle v x_3 x_4$ and $\angle x_4 x_5 v$ can be made arbitrarily small);
- $x_5 x_6 x_1 v$, which has a non-convex angle because it can be made arbitrarily close to the face $x_5 x_6 x_1 x_4$ in the non-convex embedding of $G-v+e$.
Best Answer
Edit: my initial construction was not planar, but I keep it under the line.
Take $k$ copies of $H = P_2\times P_3$. Add two adjacent vertices $u$ and $v$. Then for each copy connect $u$ with both ends of one $P_3$ and $v$ with both ends of the other $P_3$. After that for each copy except the last one add an edge between end vertex of $P_3$ adjacent to $u$ and end vertex of $P_3$ of the next copy adjacent to $v$. For inner copies two such vertices (incident to edges to the previous and to the next copies) should belong to different $P_2$'s and different $P_3$'s.
Alternative description is the following. Take $k$ copies of $8$ vertex cube. Select one edge in each of them. Contract the first ends of these edges into one vertex $v$ and the second ends of these edges into another vertex $u$. Discard multiple edges $uv$ and keep only one of them. Select two vertices other than $u$ and $v$ at distance $3$ in each copy. Add edge between selected vertex adjacent to $u$ and selected vertex of the next copy adjacent to $v$. (For the first and last copies ignore one of selected vertices, or ignore both in the only copy for $k = 1$.)
Resulting graph is planar bipartite and has $6k + 2$ vertices, $12k$ edges, $4$ vertices per face, and minimum degree $3$. Each induced cycle contains either
Take $k$ copies of the $8$ vertex cube. Select two vertices at distance $3$ in each copy. Contract all first such vertices into vertex $u$ and all second vertices into vertex $v$.
Another description of the same graph is the following: take $k$ copies of $C_6$, add two vertices $u$ and $v$ and connect $u$ with all odd vertices of each copy of $C_6$ and $v$ with all even vertices of each copy of $C_6$.
Resulting graph is bipartite and has $6k + 2$ vertices, $12k$ edges and minimum degree $3$. Each induced cycle either contains neither $u$ nor $v$ and has length $6$, or contains exactly one of $u$ and $v$ and has length $4$, or contains both $u$ and $v$, and therefore two vertices adjacent to $u$, two vertices adjacent to $v$ and no other vertex, thus also has length $6$.
P. S. For $k \ge 2$ cycle $C_6$ can be replaced by $C_4$ with the same effect or equivalently cube can be replaced by $K_{3, 3} - e$.