% Final version MAR 03 1998 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[reqno,12pt]{amsart} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Definitions ... \usepackage{enumerate} \usepackage{epic,eepic} \usepackage{geometry} % set papersize \geometry{width=6in,height=9in,top=1in,left=1in} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % algorithms ... \usepackage{float} \floatstyle{ruled} \newfloat{algorithm}{p}{loa} \usepackage[noend]{algorithmic} \renewcommand{\algorithmicrequire}{\textbf{Input:}} \renewcommand{\algorithmiccomment}[1]{\textsf{\footnotesize $/\ast$ #1 $\ast/$}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \makeatletter % headline ... \newcommand{\headline}[1]{% \def\@oddhead{% \textsc{\small#1\hfill\thepage}} \let\@evenhead\@oddhead} \addtolength{\headheight}{3.22pt} % sections in bold letters (instead small caps) ... \def\section{\@startsection{section}{1}% \z@{.7\linespacing\@plus\linespacing}{.5\linespacing}% {\normalfont\bfseries\centering}} \def\@secnumfont{\bfseries} % all lemmata, theorems, ... use the same counter \newtheorem{lemma}{Lemma} \newtheorem{thm}[lemma]{Theorem} \newtheorem{prop}[lemma]{Proposition} \newtheorem{cor}[lemma]{Corollary} % misc ... \def\precc{\prec\!\!\prec} \let\cal\mathcal \makeatother %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \headline{The electronic journal of combinatorics 5 (1998), \#R16} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{center} {\Large\bfseries Minimal Cycle Bases of Outerplanar Graphs} \bigskip\bigskip \textsc{\large Josef Leydold$^a$ and Peter F.\ Stadler$^{b,c,*}$} \bigskip\bigskip $^a$Dept.\ for Applied Statistics and Data Processing\\ University of Economics and Business Administration\\ Augasse 2-6, A-1090 Wien, Austria\\ Phone: **43 1 31336-4695 \qquad Fax: **43 1 31336-738\\ E-Mail:\quad \texttt{Josef.Leydold@wu-wien.ac.at}\\ URL: \texttt{http://statistik.wu-wien.ac.at/staff/leydold} \bigskip $^b$Institut f{\"u}r Theoretische Chemie, Universit{\"a}t Wien\\ W{\"a}hringerstra{\ss}e 17, A-1090 Wien, Austria\\ Phone: **43 1 40480 665 \qquad Fax: **43 1 40480-660\\ E-Mail:\quad \texttt{studla@tbi.univie.ac.at}\\ $^*$Address for correspondence \smallskip $^c$The Santa Fe Institute\\ 1399 Hyde Park Road, Santa Fe, NM 87501, USA\\ Phone: (505) 984 8800 \qquad Fax: (505) 982 0565\\ E-Mail:\quad \texttt{stadler@santafe.edu}\\ URL: \texttt{http://www.tbi.univie.ac.at/\~{}studla} \bigskip Submitted: July 18, 1997; Accepted: February 27, 1998. \end{center} \bigskip\bigskip\bigskip \begin{center} \begin{minipage}{0.9\textwidth} \section*{Abstract} 2-connected outerplanar graphs have a unique minimal cycle basis with length $2\vert E\vert-\vert V\vert$. They are the only Hamiltonian graphs with a cycle basis of this length. \end{minipage} \end{center} \bigskip\bigskip \textbf{Keywords:} Minimal Cycle Basis, Outerplanar Graphs \bigskip \textbf{AMS Subject Classification:} Primary 05C38. Secondary 92D20. \bigskip\bigskip\bigskip \clearpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} The description of cyclic structures is an important problem in graph theory (see e.g.\ \cite{Voss:91}). Cycle bases of graphs have a variety of applications in science and engineering, among them in structural analysis \cite{Kaveh:92} and in chemical structure storage and retrieval systems \cite{Downs:89a}. Naturally, minimal cycles bases are of particular practical interest. In this contribution we prove that outerplanar graphs have a unique minimal cycle basis. This result was motivated by the analysis of the structures of biopolymers. In addition we derive upper and lower bounds on the length of minimal cycle basis in 2-connected graphs. Biopolymers, such as RNA, DNA, or proteins form well-defined three dimensional structures. These are of utmost importance for their biological function. The most salient features of these structures are captured by their {\em contact graph} representing the set $E$ of all pairs of monomers $V$ that are spatially adjacent. While this simplification of the 3D shape obviously neglects a wealth of structural details, it encapsulates the type of structural information that can be obtained by a variety of experimental and computational methods. Nucleic acids, both RNA and DNA, form a special type of contact structures known as {\it secondary structures}. These graphs are outer-planar and subcubic, i.e., the maximal vertex degree is $3$. A particular type of cycles, which is commonly termed {\sl loops} in the RNA literature, plays an important role for RNA (and DNA) secondary structures: the energy of a secondary structure can be computed as the sum of energy contributions of the {\sl loops}. These {\sl loops} form the unique minimal cycle basis of the contact graph. Experimental energy parameters are available for the contribution of an individual {\sl loop} as a function of its size, of the type of bonds that are contained in it, and on the monomers (nucleotides) that it is composed of \cite{Freier:86}. Based on this energy model it is possible to compute the secondary structure with minimal energy given the sequence of nucleotides using a dynamic programming technique \cite{Waterman:78a}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} In this contribution we consider only finite simple graphs $G(V,E)$ with vertex set $V$ and edge set $E$, i.e., there are no loops or multiple edges. $G(V,E)$ is 2-connected if the deletion of a single vertex does not disconnect the graph. Let $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ be two sub-graphs of a graph $G(V,E)$. We shall write $G_1\setminus G_2$ for the subgraph of $G$ induced by the {\em edge set} $E_1\setminus E_2$. The set $\mathcal{E}$ of all subsets of $E$ forms an $m$-dimensional vector space over GF(2) with vector addition $X\oplus Y:=(X\cup Y)\setminus(X\cap Y)$ and scalar multiplication $1\cdot X=X$, $0\cdot X=\emptyset$ for all $X,Y\in{\cal E}$. A {\it cycle} is a subgraph such that any vertex degree is even. We represent a cycle by its edge set $C$. Sometimes it will be convenient to regard $C$ as a subgraph $(V_C,C)$ of $G(V,E)$. The set ${\cal C}$ of all cycles forms a subspace of $({\cal E},\oplus,\cdot)$ which is called the {\em cycle space} of $G$. A basis $\mathcal{B}$ of the cycle space $\mathcal C$ is called a {\em cycle basis} of $G(V,E)$ \cite{Chen:71}. The dimension of the cycle space is the {\em cyclomatic number} or {\em first Betti number} $\nu(G)=\vert E\vert - \vert V\vert +1$. It is obvious that the cycle space of graph is the direct sum of the cycle spaces of its 2-connected components. It will be sufficient therefore to consider only 2-connected graphs in this contribution. A {\em elementary cycle} is a cycle $C$ for which $(V_C,C)$ is a connected minimal subgraph such that every vertex in $V_C$ has degree $2$. We say that a cycle basis is elementary if all cycles are elementary. A cycle $C$ is a {\em chordless cycle} if $(V_C,C)$ is an induced subgraph of $G(V,E)$, i.e., if there is no edge in $E\setminus C$ that is incident to two vertices of $V_C$. We shall say that a cycle basis is chordless if all its cycles are chordless. The length $\vert C\vert$ of a cycle $C$ is the number of its edges. The length $\ell(\mathcal{B})$ of a cycle basis $\mathcal{B}$ is sum of the lengths of its cycles: $\ell(\mathcal{B}) = \sum_{C\in\mathcal{B}}\vert C\vert$. A {\it minimal cycle basis} is a cycle basis with minimal length. Let $c(\mathcal{B})$ be the length of the longest cycle in the cycle basis $\mathcal{B}$. Chickering \cite{Chickering:95} showed that if $\ell(\mathcal{B})$ is minimal then $c(\mathcal{B})$ is minimal, i.e., a minimal cycle basis has a shortest longest cycle. A cycle $C$ is {\em relevant} \cite{Plotkin:71} if it is contained in a minimal cycle basis. Vismara \cite{Vismara:97} proved the following \begin{prop}\label{relevant_cycles} A cycle $C$ is relevant if and only if it cannot be represented as a $\oplus$-sum of shorter cycles. \end{prop} An immediate consequence is \begin{cor}\label{cor:minimal=>chordless+connected} A relevant cycle is chordless. Hence a minimal cycle basis is chordless (and of course elementary). \end{cor} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Fundamental Cycle Bases} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In what follows let $G(V,E)$ be a 2-connected graph. A collection of $\nu(G)$ cycles in $G$ is called {\em fundamental} if there exists an ordering of these cycles such that \cite{Hartvigsen:89,Whitney:35} \begin{equation} \label{eq:fundamental} C_j\setminus(C_1\cup C_2\cup\dots\cup C_{j-1})\ne\emptyset \qquad\mbox{for }2\le j\le\nu(G) \end{equation} Of course such a collection is a cycle basis. Not all cycle bases are fundamental \cite{Hartvigsen:89}. \begin{lemma}\label{lemma:fundamental} An elementary fundamental cycle basis can be ordered such that \begin{enumerate}[(i)] \item $C_1$ is an elementary cycle and \item $C_j\setminus (C_1\cup\dots\cup C_{j-1}) = P_j$ is a nonempty path for $2\leq j\leq \nu(G)$. \end{enumerate} \end{lemma} \begin{proof} Let $G_i=C_1\cup\dots\cup C_i$. Then $\nu(G_i)\geq \nu(G_{i-1})+1$ for $i\geq 2$ and consequently $\nu(G)=\nu(G_{\nu(G)})\geq \nu(G_{\nu(G)-1})+1 \geq\dots\geq \nu(G_1) + (\nu(G)-1) = \nu(G)$. Therefore equality holds and we have $\nu(G_i)=i$, i.e.\ $\mathcal{B}_i=\{C_1,\ldots,C_i\}$ is a cycle basis for $G_i$. Next notice that there exists an ordering for which (\ref{eq:fundamental}) holds such that $G_i$ is connected for all $i\geq 1$, i.e.\ $C_i\cap G_{i-1}\ne\emptyset$. Otherwise there exists a $j$ such that $C\cap G_j=\emptyset$ for all $C\in\mathcal{B}\setminus\mathcal{B}_{j-1}$ for all orderings satisfying (\ref{eq:fundamental}). But then $C_j\cup\dots\cup C_{\nu(G)}$ has empty intersection with $G_{j-1}=C_1\cup\dots\cup C_{j-1}$, a contradiction, since $G=C_1\cup\dots\cup C_{\nu(G)}$ is 2-connected. $G_i$ is connected since by assumption all $C_j$ are elementary. An immediate consequence is that $C_j\setminus G_{j-1}$ must be either a path as claimed, or an elementary cycle which has one vertex in common with $G_{j-1}$. Otherwise we would have $\nu(G_j)>j$. If $C_j\setminus G_{j-1}$ is a cycle, this one vertex must be a cut vertex of $G_j$. In this case, there must be a list of cycles $C_{k_1}$, $C_{k_2}$, $\dots$, $C_{k_p}$ in $B\setminus B_j$ such that: $C_{k_1}$ has edges in common with $G_{j-1}$, $C_{k_q}$ has edges in common with $C_{k_{q+1}}$ for all $q\in[1, p-1]$, and $C_{k_p}$ has edges in common with $C_j$. Then we can reorder the basis by exchanging $C_j$ and $C_k$. \end{proof} A weaker result holds for non-fundamental cycle bases: \begin{lemma}\label{lemma:nonfundamental} Any elementary non-fundamental cycle basis can be ordered such that $C_1\cup\ldots\cup C_i$ is 2-connected for all $i\geq 1$. \end{lemma} \begin{proof} Analogously to the proof of lemma~\ref{lemma:fundamental} there exists an ordering such that $G_i$ is connected for all $i\geq 1$, i.e.\ $C_i\cap G_{i-1}\ne\emptyset$. Otherwise there exists a $j$ such that $C\cap G_j=\emptyset$ for all $C\in\mathcal{B}\setminus\mathcal{B}_{j-1}$ for all orderings. But then $C_j\cup\dots\cup C_{\nu(G)}$ has empty intersection with $G_{j-1}=C_1\cup\dots\cup C_{j-1}$, a contradiction, since $G=C_1\cup\dots\cup C_{\nu(G)}$ is 2-connected. $G_i$ is connected since by assumption all $C_j$ are elementary. Similarly there exists an ordering such that $G_i$ is 2-connected for all $i\geq 1$. Obviously $G_1=C_j$ is 2-connected, since $C_j$ is elementary. Assume $G_{j-1}$ is 2-connected. If $C_j\cap G_{j-1}$ consists of at least two vertices, $G_j$ is 2-connected. If $C_j$ and $G_{j-1}$ have only one vertex in common (there must be at least one such vertex), then there must be a cycle $C_k\in\mathcal{B}\setminus\mathcal{B}_j$ which has edges in common with $G_{j-1}$ and with $P_j$. Otherwise $G$ cannot be 2-connected. Then we can reorder the basis by exchanging $C_j$ and $C_k$. \end{proof} If $\mathcal{B}$ is a non-fundamental cycle basis of $G$ then there is subgraph $G'$ with cycle basis $\mathcal{B}'\subseteq\mathcal{B}$ such that each edge of $G'$ is contained in at least two cycles of $\mathcal{B}'$ \cite[prop.~4.2]{Hartvigsen:89}. Furthermore, the examples of non-fundamental bases in \cite{Hartvigsen:89} are much longer than the minimal cycles bases. One might be tempted therefore to conjecture that every minimal cycle basis is fundamental. Although this statement is easily verified for planar graphs (see corollary~\ref{cor:planar+minimal=>fundamental}), it is not true in general: Consider the complete graph $K_9$ with 9 vertices. It is straightforward (we used {\tt Mathematica}) to check that the following 28 cycles are independent and thus are a basis of the cycle space, since $\nu(K_9)=28$. \begin{center} \begin{tabular}{l} $(1,2,3), (2,3,4), (1,3,5), (3,4,5), (2,4,5), (2,5,6), (1,5,6),$\\ $ (1,4,6), (3,4,6), (2,6,7), (3,6,7), (1,3,7), (1,4,7), (4,5,7),$\\ $ (2,7,8), (5,7,8), (1,5,8), (1,6,8), (4,6,8), (2,3,8), (3,8,9),$\\ $ (4,8,9), (1,4,9), (1,2,9), (2,5,9), (5,6,9), (6,7,9), (3,7,9)$\\ \end{tabular} \end{center} Here $(1,2,3)$ denotes the 3-cycle $\{(v_1,v_2),(v_2,v_3),(v_3,v_1)\}$. This basis is minimal, since every cycle has length 3. But it is non-fundamental, since every edge is covered at least two times. The concept of \emph{fundamental} has originally been introduced by Kirchhoff in 1847 \cite{Kirchhoff:1847} in the following way: Suppose $T$ is a spanning tree of $G$. Then for each edge $\alpha\notin T$ there is unique cycle in $T\cup\{\alpha\}$ which is called a {\it fundamental cycle}. The set of fundamental cycles belonging to a given spanning tree form a basis of the cycle subspace which is called the {\it fundamental basis w.r.t.\ $T$}. For details see \cite{Thulasiraman:92}. It is obvious that a fundamental basis w.r.t.\ a spanning tree is a special case of the fundamental collections defined at the beginning of this section, see also \cite{Hartvigsen:89}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Outerplanar Graphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% A graph $G(V,E)$ is {\em outer-planar} if it can be embedded in the plane such that all vertices lie on the boundary of its exterior region. Given such an embedding we will refer to the set of edges on the boundary to the exterior region as the {\em boundary} $B$ of $G$. A graph is outerplanar if and only if it does not contain a $K_4$ or $K_{3,2}$ minor \cite{Chartrand:67}. An algebraic characterization in terms of a spectral invariant is discussed in \cite{ColinVerdiere:90}. \begin{lemma} An outerplanar graph $G(V,E)$ is Hamiltonian if and only if it is 2-connected. \end{lemma} \begin{proof} A Hamiltonian graph is always 2-connected. Suppose $G$ is outerplanar, 2-connected, but not Hamiltonian. 2-connectedness implies that there is no cut-vertex. Thus the boundary $B$ of $G$ is a closed path containing an edge at most once. A vertex $x$ that is incident with more than 2 edges of $B$ must be a cut-vertex of $G$ since it partitions $B$ into (at least) two edge-disjoint closed paths $B'$ and $B''$. Let $V'$ and $V''$ the vertices incident with the edges in $B'$ and $B''$, respectively. Outerplanarity implies that there are no edges connecting a vertex $y\in V'\setminus\{x\}$ with a vertex $z\in V''\setminus\{x\}$. Thus $x$ is a cut vertex, contradicting 2-connectedness. \end{proof} \begin{lemma} A 2-connected outerplanar graph $G(V,E)$ contains a unique Hamiltonian cycle $H$. \end{lemma} \begin{proof} If $G$ is a cycle graph, there is nothing to show. Otherwise denote by $H$ the Hamiltonian cycle forming the boundary of $G$ and consider an arbitrary edge $\alpha\notin H$. By construction $G$ is embedded in the plane such that $\alpha=(p,q)$ divides $G$ into two subgraphs $G_1$ and $G_2$ with vertex sets $V_1$ and $V_2$ satisfying $\vert V_i\vert\ge3$ and $V_1\cap V_2=\{p,q\}$. Now consider two vertices $x\in V_1\setminus\{p,q\}$ and $y\in V_2\setminus\{p,q\}$. Since $G$ is outerplanar, each path from $x$ to $y$ passes through $p$ or $q$. Each elementary cycle containing both $x$ and $y$ therefore consists of two disjoint paths, one of which passes only through $p$ while the other one passes only through $q$. Thus the edge $(p,q)$ cannot be part of any elementary cycle containing both $x$ and $y$, and hence $G$ contains no Hamiltonian cycle different from $H$. \end{proof} As a consequence there is a unique partition of the edge set $E$ of an outerplanar graph $G$ into the Hamiltonian cycle $H$ and the {\em set of chords} $K=E\setminus H$. It will be convenient to label the vertices such that the edges in $H$ are $(i,i+1)$ for $1\le i\le n-1$ and $(1,n)$. Without loosing generality we may assume that $n$ is a vertex of degree $2$. It will be useful to introduce the following partial order on $K$: \begin{equation} \alpha =(i_\alpha,j_\alpha) \prec \beta=(i_\beta,j_\beta) \quad\mbox{ if and only if }\quad i_\beta\le i_\alpha < j_\alpha\le j_\beta \,\,\mbox{and}\,\, \alpha\ne\beta\,. \end{equation} We say that $\alpha$ is {\it interior to} $\beta$. If there is no $\gamma\in K$ such that $\alpha\prec\gamma\prec\beta$ we say that $\alpha$ is immediately interior to $\beta$, $\alpha\precc\beta$. For each alpha in $K$ we set $Y_\alpha=\{\beta\in K\vert \beta\prec\prec\alpha\}$. $Y_*$ denotes the set of $\prec$-maximal elements in $K$, i.e., the set of contacts that are not interior to any other contact. Yan's \cite{Yan:95} {\em bamboo shoot graphs} are exactly those outer-planar graphs for which $(K,\prec)$ is an ordered set. Nucleic acids, both RNA and DNA, form a special type of contact structure known as {\em secondary structure}. A graph $G(V,E)$, with $V=\{1,\dots,n\}$, is a secondary structure if it satisfies \begin{enumerate}[(i)] \item The so-called backbone $T=\{(i,i+1)\vert 1\le i k_2 > \ldots > i+1$} \STATE push edge $(i,k_j)$ on stack. \ENDFOR \ENDFOR \end{algorithmic} \end{algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[p] \begin{center} \leavevmode \setlength{\unitlength}{0.08mm} \begin{picture}(505,555)(0,-10) \put(165,435){\blacken\ellipse{30}{30}} \put(445,315){\blacken\ellipse{30}{30}} \put(445,155){\blacken\ellipse{30}{30}} \put(325,35){\blacken\ellipse{30}{30}} \put(165,35){\blacken\ellipse{30}{30}} \put(45,155){\blacken\ellipse{30}{30}} \put(45,315){\blacken\ellipse{30}{30}} \put(323,433){\blacken\ellipse{30}{30}} \path(165,435)(325,435)(445,315)(445,155)(325,35)(165,35)(45,155)(45,315)(165,435) \path(45,315)(325,435) \path(325,35)(45,315) \path(325,35)(45,155) \path(325,35)(445,315) \path(325,35)(325,435) \put(0,285){\makebox(0,0)[lb]{$8$}} \put(0,110){\makebox(0,0)[lb]{$7$}} \put(120,0){\makebox(0,0)[lb]{$6$}} \put(345,5){\makebox(0,0)[lb]{$5$}} \put(465,130){\makebox(0,0)[lb]{$4$}} \put(440,340){\makebox(0,0)[lb]{$3$}} \put(340,455){\makebox(0,0)[lb]{$2$}} \put(175,460){\makebox(0,0)[lb]{$1$}} \end{picture} \mbox{}\\ \begin{tabular}{cclll} $i$ & step & action & \multicolumn{1}{c}{{\tiny bottom}\hspace{2em}stack\hspace{2em}{\tiny top}} & \multicolumn{1}{c}{$V$} \\[0.5ex] & 0 & beginn & empty & empty \\ & 1 & make list & empty & $(1,2,3,4,5,6,7,8)$ \\ 1 & 9 & push $(1,8)$ & $(1,8)$ & $(1,2,3,4,5,6,7,8)$ \\ 2 & 9 & push $(2,8)$ & $(1,8),(2,8)$ & $(1,2,3,4,5,6,7,8)$ \\ 2 & 9 & push $(2,5)$ & $(1,8),(2,8),(2,5)$ & $(1,2,3,4,5,6,7,8)$ \\ 3 & 9 & push $(3,5)$ & $(1,8),(2,8),(2,5),(3,5)$ & $(1,2,3,4,5,6,7,8)$ \\ 4 & & none & $(1,8),(2,8),(2,5),(3,5)$ & $(1,2,3,4,5,6,7,8)$ \\ 5 & 4--7 & create $(3,4,5,3)$ & $(1,8),(2,8),(2,5)$ & $(1,2,3,5,6,7,8)$ \\ 5 & 4--7 & create $(2,3,5,2)$ & $(1,8),(2,8)$ & $(1,2,5,6,7,8)$ \\ 5 & 9 & push $(5,8)$ & $(1,8),(2,8),(5,8)$ & $(1,2,5,6,7,8)$ \\ 5 & 9 & push $(5,7)$ & $(1,8),(2,8),(5,8),(5,7)$ & $(1,2,5,6,7,8)$ \\ 6 & & none & $(1,8),(2,8),(5,8),(5,7)$ & $(1,2,5,6,7,8)$ \\ 7 & 4--7 & create $(5,6,7,5)$ & $(1,8),(2,8),(5,8)$ & $(1,2,5,7,8)$ \\ 8 & 4--7 & create $(5,7,8,5)$ & $(1,8),(2,8)$ & $(1,2,5,8)$ \\ 8 & 4--7 & create $(2,5,8,2)$ & $(1,8)$ & $(1,2,8)$ \\ 8 & 4--7 & create $(1,2,8,1)$ & empty & $(1,8)$ \\ & & stop & & \end{tabular} \caption{Example for algorithm~\ref{alg:minimal}} \label{fig:algorithm} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The basic idea of algorithm~\ref{alg:minimal} is to find the minimal cycles $C_\alpha$ described in the proof of theorem~\ref{thm:minimal_of_outerplanar}. When such a cycle is found, it is added to the cycle basis and ``chopped off'' the graph. Step~1 generates an ordered list of $V$ (along the Hamiltonian cycle). It is best implemented as linked list of pointers to the vertices. Steps~8 and 9 push every contact (and $(1,n)$) that have not already been processed on the stack. Steps~3 and 4 pop all contacts incident to the current vertex $i$ from the stack. By corollary~\ref{cor:length_outerplanar} the ordering of the edges used in step~8 ensures that the cycle generated in steps~5 and 6 are chordless and all vertices except $i$ and $k_j$ in $P$ have degree~2. Hence they are part of $\mathcal{M}$. In step step~7 they are ``chops off'' taking advantage of the fact that $V$ is a linked list. It is easy to see that this algorithm is of order $O(|V|)$. We illustrate the algorithm in Figure~\ref{fig:algorithm}. It is interesting to note that the fundamental basis ${\cal F}$ can be easily expressed in terms of the minimal cycle basis ${\cal M}$: \[ \begin{array}{l} F_\alpha = C_\alpha\oplus \left[\bigoplus_{\beta\in Y_\alpha} F_\beta\right] = C_\alpha\oplus \left[\bigoplus_{\beta\in Y_\alpha} C_\beta \oplus \left[\bigoplus_{\gamma\in Y_\beta} F_\gamma \right] \right] \\ \qquad = C_\alpha\oplus \left[\bigoplus_{\beta\in Y_\alpha} C_\beta \oplus \left[\bigoplus_{\gamma\in Y_\beta} C_\gamma \oplus \left[\bigoplus_{\delta\in Y_\gamma} F_\delta \right] \right] \right] = \dots \end{array} \] The expansion eventually stops if $Y_\psi=\emptyset$ and hence $F_\psi=C_\psi$. Clearly, the nested sums contain each bond in $W_\alpha = \{\beta\in K\vert \beta\prec\alpha\}$, the set of contacts interior to $\alpha$, and $\alpha$ itself exactly once. Therefore we have $$F_\alpha= \bigoplus_{\beta\in W_\alpha\cup\{\alpha\}} C_\beta\,.$$ Analogously one finds $$H = \left[\bigoplus_{\beta\in Y_*} F_\beta\right]\oplus C_* = \left[\bigoplus_{\beta\in K} C_\beta\right] \oplus C_* \,. $$ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Upper Bounds on $\boldsymbol{\min\ell(\mathcal{B})}$} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In \cite[theorem 6]{Horton:87} an upper bound for the length of a minimal cycle basis $\mathcal{M}$ of an arbitrary graph $G(V,E)$ is given: \begin{equation} \ell(\mathcal{M}) \le 3(\vert V\vert-1)(\vert V\vert-2)/2. \end{equation} While this bound is sharp for complete graphs \cite{Deo:82}, it can be improved substantially for planar graphs. First we need the following simple observations: \begin{prop}\label{lemma:edges_upperbound} Let $G(E,V)$ be a 2-connected graph. Then \begin{eqnarray} \label{eq:edges_upperbound_planar} |E| \leq 3\,|V| - 6 && \mbox{if $G$ is planar.}\\[1ex] \label{eq:edges_upperbound_outer} |E| \leq 2\,|V| - 3 && \mbox{if $G$ is outerplanar.} \end{eqnarray} These bounds are sharp for all $\vert V\vert\ge3$. \end{prop} The result on planar graphs is an immediate corollary of Euler's formula for polyhedra. The upper bound on outerplanar graphs follows from a theorem by G.A.\ Dirac \cite{Dirac:60} stating that for any graph not containing $K_4$ as a minor we have $|E| \le 2 |V| -3$. A bamboo-shoot graph \cite{Yan:95} consisting of $n$ triangles has $n'=n+2$ vertices and $2n+1=2n'-3$ edges. Consider the graph $G_n$ recursively obtained by adding a vertex $n$ which is connected to the three vertices labeled $n-1$, $1$, and $2$ of $G_{n-1}$. We set $G_3=K_3$, the cycle of length $3$. It is obvious that these graphs are all planar, and $G_n$ has $3$ edges and $1$ vertex more than $G_{n-1}$. Thus $G_n$ has $n$ vertices and $3(n-3)+3=3n-6$ edges. We can translate the above result into upper bounds for the lengths of a minimal cycle bases that depend only on the number of vertices: \begin{thm}\label{lemma:length_upperbound} Let $G(E,V)$ be a 2-connected planar graph with a minimal cycle basis $\mathcal{M}$. Then \begin{eqnarray} \label{eq:length_upperbound_planar} \ell(\mathcal{M}) \leq 6\,|V| - 15 && \mbox{if $G$ is planar.}\\[1ex] \label{eq:length_upperbound_outer} \ell(\mathcal{M}) \leq 3\,|V| - 6 && \mbox{if $G$ is outerplanar.} \end{eqnarray} \end{thm} \begin{proof} Analogously to the proof of proposition~\ref{lemma:edges_upperbound} we find for the planar case $\ell(\mathcal{M}) \leq 2\,|E| - 3 \leq 2\,(3\,|V|-6) - 3 =6\,|V|-15$ by (\ref{eq:edges_upperbound_planar}) as claimed. Similarly for the outer planar case: $\ell(\mathcal{M}) = 2\,|E| - |V| \leq 2(2\,|V| - 3)-|V| = 3\,|V|-6$ which is (\ref{eq:length_upperbound_outer}). \end{proof} \begin{figure}[htbp] \begin{center} \leavevmode %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \setlength{\unitlength}{0.004mm} \begin{picture}(9619,9328)(0,-10) \thicklines \put(3548.647,3422.706){\arc{4606.427}{1.2927}{4.1807}} \put(6178.693,2416.978){\arc{4670.077}{6.0604}{8.8806}} \put(7319.461,5038.769){\arc{4582.963}{4.3843}{7.3723}} \put(4181,7208){\blacken\ellipse{300}{300}} \put(8381,5408){\blacken\ellipse{300}{300}} \put(8381,3008){\blacken\ellipse{300}{300}} \put(6581,1208){\blacken\ellipse{300}{300}} \put(4181,1208){\blacken\ellipse{300}{300}} \put(4626.771,6059.880){\arc{4533.074}{2.8499}{5.7520}} \put(2381,3008){\blacken\ellipse{300}{300}} \path(6581,7283) (6598.871,7357.116) (6615.354,7428.671) (6630.445,7497.730) (6644.134,7564.358) (6656.417,7628.622) (6667.285,7690.585) (6676.733,7750.313) (6684.752,7807.872) (6691.337,7863.326) (6696.480,7916.742) (6700.175,7968.183) (6702.414,8017.716) (6703.191,8065.405) (6702.499,8111.316) (6700.331,8155.514) (6696.680,8198.064) (6691.539,8239.031) (6684.902,8278.482) (6667.111,8353.092) (6643.251,8422.415) (6613.268,8486.974) (6577.106,8547.290) (6534.711,8603.885) (6486.027,8657.281) (6431.000,8708.000) \path(6431,8708) (6375.565,8753.592) (6319.152,8796.873) (6261.796,8837.878) (6203.533,8876.643) (6144.398,8913.206) (6084.427,8947.603) (6023.654,8979.870) (5962.115,9010.043) (5899.845,9038.160) (5836.879,9064.256) (5773.253,9088.368) (5709.001,9110.532) (5644.160,9130.785) (5578.764,9149.163) (5512.849,9165.703) (5446.449,9180.441) (5379.601,9193.413) (5312.339,9204.657) (5244.699,9214.208) (5176.715,9222.103) (5108.424,9228.378) (5039.860,9233.069) (4971.059,9236.214) (4902.056,9237.849) (4832.886,9238.009) (4763.584,9236.732) (4694.186,9234.054) (4624.727,9230.011) (4555.242,9224.640) (4485.767,9217.978) (4416.337,9210.059) (4346.986,9200.923) (4277.751,9190.603) (4208.666,9179.138) (4139.767,9166.562) (4071.090,9152.914) (4002.668,9138.229) (3934.538,9122.544) (3866.735,9105.895) (3799.294,9088.319) (3732.250,9069.851) (3665.639,9050.529) (3599.495,9030.389) (3533.855,9009.467) (3468.753,8987.800) (3404.225,8965.425) (3340.305,8942.377) (3277.030,8918.693) (3214.434,8894.409) (3152.553,8869.563) (3091.422,8844.190) (3031.076,8818.327) (2971.550,8792.010) (2912.880,8765.276) (2855.101,8738.161) (2798.248,8710.701) (2742.357,8682.934) (2687.462,8654.895) (2633.599,8626.621) (2580.804,8598.148) (2529.111,8569.514) (2478.556,8540.753) (2429.174,8511.903) (2381.000,8483.000) \path(2381,8483) (2336.214,8454.793) (2291.743,8424.858) (2247.595,8393.241) (2203.775,8359.992) (2160.291,8325.156) (2117.149,8288.783) (2074.355,8250.920) (2031.918,8211.615) (1989.843,8170.915) (1948.138,8128.869) (1906.808,8085.524) (1865.861,8040.928) (1825.303,7995.129) (1785.142,7948.174) (1745.383,7900.111) (1706.034,7850.988) (1667.102,7800.853) (1628.592,7749.754) (1590.512,7697.738) (1552.869,7644.853) (1515.669,7591.147) (1478.919,7536.668) (1442.626,7481.463) (1406.797,7425.581) (1371.437,7369.068) (1336.555,7311.974) (1302.156,7254.345) (1268.248,7196.229) (1234.837,7137.674) (1201.929,7078.729) (1169.533,7019.440) (1137.654,6959.855) (1106.299,6900.023) (1075.474,6839.990) (1045.188,6779.806) (1015.446,6719.517) (986.254,6659.171) (957.621,6598.817) (929.552,6538.501) (902.054,6478.272) (875.135,6418.178) (848.800,6358.266) (823.056,6298.583) (797.911,6239.179) (773.370,6180.100) (749.442,6121.394) (726.132,6063.110) (703.446,6005.294) (681.393,5947.995) (659.979,5891.261) (639.209,5835.139) (619.092,5779.677) (599.634,5724.922) (580.841,5670.923) (562.720,5617.728) (545.279,5565.383) (528.523,5513.937) (512.460,5463.438) (497.096,5413.934) (482.438,5365.472) (468.492,5318.099) (455.267,5271.865) (442.767,5226.816) (431.000,5183.000) \path(431,5183) (418.141,5134.042) (405.015,5083.539) (391.657,5031.537) (378.101,4978.084) (364.382,4923.227) (350.534,4867.013) (336.592,4809.491) (322.590,4750.707) (308.562,4690.709) (294.544,4629.544) (280.569,4567.260) (266.671,4503.903) (252.887,4439.523) (239.249,4374.165) (225.792,4307.877) (212.551,4240.707) (199.560,4172.702) (186.854,4103.910) (174.467,4034.377) (162.433,3964.152) (150.787,3893.281) (139.564,3821.812) (128.798,3749.793) (118.523,3677.271) (108.774,3604.293) (99.586,3530.907) (90.992,3457.159) (83.027,3383.099) (75.726,3308.772) (69.123,3234.226) (63.252,3159.510) (58.149,3084.669) (53.847,3009.751) (50.381,2934.805) (47.785,2859.877) (46.094,2785.015) (45.343,2710.265) (45.565,2635.677) (46.795,2561.296) (49.068,2487.170) (52.418,2413.348) (56.880,2339.875) (62.488,2266.800) (69.276,2194.170) (77.279,2122.032) (86.531,2050.434) (97.068,1979.423) (108.922,1909.046) (122.130,1839.352) (136.724,1770.386) (152.741,1702.198) (170.213,1634.834) (189.176,1568.341) (209.664,1502.767) (231.711,1438.160) (255.353,1374.566) (280.622,1312.033) (307.555,1250.609) (336.185,1190.341) (366.547,1131.277) (398.675,1073.463) (432.603,1016.947) (468.367,961.777) (506.000,908.000) \path(506,908) (553.728,846.091) (605.186,786.362) (660.176,728.828) (718.502,673.504) (779.966,620.405) (844.372,569.546) (911.522,520.942) (981.219,474.608) (1053.267,430.560) (1127.469,388.813) (1165.316,368.806) (1203.627,349.381) (1242.378,330.538) (1281.544,312.280) (1321.101,294.608) (1361.024,277.525) (1401.288,261.032) (1441.870,245.131) (1482.743,229.824) (1523.883,215.113) (1565.267,201.000) (1606.869,187.486) (1648.664,174.574) (1690.629,162.266) (1732.737,150.563) (1774.966,139.467) (1817.289,128.980) (1859.683,119.105) (1902.123,109.842) (1944.585,101.194) (1987.042,93.163) (2029.472,85.750) (2071.849,78.958) (2114.149,72.789) (2156.347,67.243) (2198.419,62.324) (2240.339,58.032) (2282.084,54.371) (2323.628,51.342) (2364.947,48.946) (2406.017,47.185) (2446.812,46.063) (2487.309,45.579) (2527.482,45.737) (2567.306,46.538) (2606.758,47.984) (2645.813,50.077) (2684.446,52.819) (2722.632,56.211) (2760.346,60.256) (2834.263,70.312) (2906.000,83.000) \path(2906,83) (2976.315,99.564) (3045.700,121.372) (3114.623,148.836) (3183.551,182.367) (3252.950,222.378) (3323.288,269.282) (3395.031,323.489) (3468.646,385.411) (3506.302,419.395) (3544.601,455.462) (3583.601,493.664) (3623.361,534.052) (3663.940,576.678) (3705.395,621.594) (3747.785,668.851) (3791.168,718.500) (3835.603,770.593) (3881.149,825.181) (3927.862,882.317) (3975.803,942.051) (4025.028,1004.434) (4075.598,1069.519) (4127.569,1137.358) (4181.000,1208.000) \put(2381,5408){\blacken\ellipse{300}{300}} \put(2381,5408){\ellipse{300}{300}} \put(6551,7178){\blacken\ellipse{300}{300}} \put(6551,7178){\ellipse{300}{300}} \put(5381,4208){\blacken\ellipse{300}{300}} \put(5381,4208){\ellipse{300}{300}} \path(4181,7208)(6581,7208)(8381,5408) (8381,3008)(6581,1208)(4181,1208) (2381,3008)(2381,5408)(4181,7208) \path(4181,7208)(6581,1208) \path(6581,7208)(4181,1208) \path(2306,5408)(8381,3008) \path(2306,3008)(8381,5408) \end{picture} \caption{A Hamiltonian planar graph for which inequality~(\ref{eq:length_upperbound_planar}) is sharp.} \label{fig:plan8} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% It is not possible to improve the bound (\ref{eq:length_upperbound_planar}) for planar Hamiltonian graphs, see the example in figure~\ref{fig:plan8}. Similar examples for $\vert V\vert=2^m+1$ can be constructed by the following recipe: \begin{enumerate}[1.] \item Start with a $2^m$-gon. \item Insert the center as additional vertex $c$ and add edges $(c,i)$ for $1\leq i\leq 2^m$. \item Insert edges $(1,3)$, $(3,5)$, $(5,7)$, \ldots. \item Insert edges $(1,5)$, $(5,9)$, $(9,13)$, \ldots, and so on. \end{enumerate} \begin{lemma}\label{lemma:upper_bound_outerplanar} Let $G(V,E)$ be a 2-connected planar graph. Then $\ell(\mathcal{M})\le 2|E|-g(G)$, where $g(G)$ denotes the girth of $G$. \end{lemma} \begin{proof} A planar cycle basis contains each ``interior'' edge twice, while the edges of the outer boundary appear only once. The length of the outer boundary is at least $g(G)$. \end{proof} As an immediate consequence we have \begin{cor}\label{cor:planar+minimal=>fundamental} Every minimal cycle basis of a planar graph is fundamental. \end{cor} \begin{proof} Suppose $\mathcal{B}$ is not fundamental. By \cite[prop.~4.2]{Hartvigsen:89} we can assume that here is a subset $\mathcal{B}'\subseteq\mathcal{B}$ such that (i) $\mathcal{B}'$ is a minimal cycle basis for $G'$, the subgraph of $G$ induced by $\mathcal{B}'$, and (ii) $\mathcal{B}'$ covers every edge of $G'$ two or more times. We can assume that $G'$ is 2-connected; otherwise consider $G''$ with minimal cycle basis $\mathcal{B}''$ where $G''$ is a 2-connected subgraph of $G'$ with minimal cycle basis $\mathcal{B}''\subseteq\mathcal{B}'$ is a subset. (Note that $\mathcal{B}''$ necessarily covers every edge of $G''$ two or more times.) Thus $\ell(\mathcal{B}')\geq 2|E'|$. But since every planar cycle basis has length $\ell(\mathcal{B})< 2|E|$ by lemma~\ref{lemma:upper_bound_outerplanar}, $\mathcal{B}'$ cannot be a minimal cycle basis of $G'$, and the proposition follows. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Lower Bounds on $\boldsymbol{\ell(\mathcal{B})}$} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thm}\label{thm:lower-bound} Let $G(V,E)$ be a 2-connected graph and $\mathcal{B}$ a cycle basis of $G$. Then \begin{equation} \label{eq:lower-bound} \ell(\mathcal{B})\ge 2|E|-|V| \end{equation} If equality holds, then the cycle basis $\mathcal{B}$ is minimal. Equality holds for a basis if and only if for every vertex $v\in V$ the number of cycles $c\in\mathcal{B}$ through $v$ is $d_v-1$, where $d_v$ denotes the degree of $v$. \end{thm} \begin{proof} Let $S_v$ denote the graph induced by all edges incident to $v$ ($S_v$ is a star of diameter 2 with $d_v$ edges). The edge set $E_v$ of $S_v$ with the addition $\oplus$ forms a $d_v$-dimensional vector space. Let $\mathcal{T}_v$ denote its sub space where each element consists of an even number of edges. As can easily be verified, $\dim(\mathcal{T}_v)=d_v-1$. Let $\mathcal{C}_v$ denote the vector space $(\{C\cap S_v\colon C\in\mathcal{C}\},\oplus,\cdot)$. It is obvious that $\mathcal{C}_v\subseteq\mathcal{T}_v$. Moreover for all $C\in\mathcal{C}_v$ that consists of exactly 2 edges, there exists a $C'\in\mathcal{C}$ with $C=C'\cap S_v$ and thus $\mathcal{C}_v\supseteq\mathcal{T}_v$. Otherwise every cycle $C$ in $G$ has vertex $v$ as double point and hence $v$ was a cut vertex of $G$, a contradiction to $G$ being 2-connected. Therefore $\mathcal{C}_v=\mathcal{T}_v$ is spanned by $\mathcal{B}_v = \{C\cap S_v\colon C\in\mathcal{B}, C\cap S_v\not=\emptyset\}$. Consequently $|\mathcal{B}_v|\geq\dim(\mathcal{T}_v)=d_v-1$ and $\ell(\mathcal{B}_v)\geq 2\,d_v-2$, since every $C\in\mathcal{B}$ contains at least two edges. Notice that $|E|=\frac{1}{2}\sum_{v\in V} d_v$ (every edge is incident to 2 vertices) and $\ell(\mathcal{B}) = \frac{1}{2}\sum_{v\in V}\ell(\mathcal{B}_v)$ (every edge is contained in the stars $S_{v_i}$ centered at two vertices $v_1$ and $v_2$). Hence we find \[ \ell(\mathcal{B}) = \frac{1}{2}\sum_{v\in V}\ell(\mathcal{B}_v) \geq \sum_{v\in V} (d_v-1) = 2\,|E|-|V| \] i.e., inequality (\ref{eq:lower-bound}). Equality holds if and only if $\mathcal{B}_v$ is a basis of $\mathcal{T}_v$. Thus the statement follows. \end{proof} \begin{thm}\label{thm:equality=>fundamental} Let $G(V,E)$ be a 2-connected graph with a elementary cycle basis $\mathcal{B}$. Then $\ell(\mathcal{B})= 2|E|-|V|$ if and only if $\mathcal{B}$ is a fundamental cycle basis such that $|C_i\cap(C_1\cup\cdots\cup C_{i-1})|=1$ for all $2\leq i\leq\nu(G)$ (i.e.\ consists of exactly one edge). In this case $\mathcal{B}$ is a minimal cycle basis. \end{thm} \begin{proof} By lemmata~\ref{lemma:fundamental} and \ref{lemma:nonfundamental} we can order the cycle basis $\mathcal{B}$ such that $C_1\cup\dots\cup C_i$ is 2-connected. Thus $C_i\cap (C_1\cup\dots\cup C_{i-1})$ consists of at least one edge. Let $\phi(G)=2|E|-|V|$. Let $E_i$ denote the edge set of $G_i$ and let $V_i$ and $V(C_j)$ denote the vertex sets of $G_i$ and $C_j$, respectively. Then we find \begin{eqnarray*} \phi(G_i) &=&2|E_i|-|V_i| \\ &=&2(|E_{i-1}| + |C_i| - |E_{i-1}\cap C_i|) - (|V_{i-1}| + |V(C_i)| - |V_{i-1}\cap V(C_i)|) \\ &=&(2|E_{i-1}| - |V_{i-1}|) \!+\! (2|C_i| - |V(C_i)|) - (2|E_{i-1}\cap C_i| - |V_{i-1}\cap V(C_i)|) \\ &=&\phi(G_{i-1}) + |C_i| - (|E_{i-1}\cap C_i|-\eta_i) \end{eqnarray*} since $|C_i|=|V(C_i)|$ and $|V_{i-1}\cap V(C_i)|=|E_{i-1}\cap C_i| + \eta_i$, where $\eta_i$ denotes the number of connected components (i.e.\ paths) in $C_i\setminus E_{i-1}$. The latter equality holds because $C_i$ is elementary. Notice that the number of components in $C_i\cap E_{i-1} = \eta_i$ if $\eta_i\geq 1$ and $1$ otherwise, since $C_i$ is elementary. Thus $|E_{i-1}\cap C_i| \geq \eta_i$ and \[ \phi(G_i) \leq \phi(G_{i-1}) + |C_i| \] Equality holds if and only if $|E_{i-1}\cap C_i|=\eta_i$. Let $\mathcal{B}_i=\{C_1,\ldots,C_i\}$. We have $\ell(\mathcal{B}_1)=|C_1|=2|E_1|-|V_1|=\phi(G_1)$ since $C_1$ is an elementary cycle. By induction we then find $\ell(\mathcal{B}_i)\geq \phi(G_i)= 2|E_i|-|V_i|$: \[ \ell(\mathcal{B}_i)=\ell(\mathcal{B}_{i-1})+|C_i| \geq \phi(G_{i-1})+|C_i|\geq\phi(G_i) \] Equality holds if and only if all $|E_{i-1}\cap C_i|=\eta_i$. If $\mathcal{B}$ is fundamental then $\eta_i=1$ for all $i$ by lemma~\ref{lemma:fundamental} and $E_{i-1}\cap C_i$ is a single edge for all $i$ as claimed. If $\mathcal{B}$ is not fundamental, than we always have an $j$ such that $C_j\subseteq E_{j-1}$ and thus $|E_{j-1}\cap C_j|=|C_j|>0=\eta_j$. Thus $\ell(\mathcal{B}_j)>\phi(G_j)$. Moreover, if $\ell(\mathcal{B})= 2|E|-|V|$ then, by theorem~\ref{thm:lower-bound}, $\mathcal{B}$ is a minimal cycle basis. \end{proof} In the following we derive some weaker conditions for which (\ref{eq:lower-bound}) is sharp. \begin{lemma}\label{lemma:2-connected+equality} Let $G(V,E)$ be a 2-connected graph. If $\ell(\mathcal{B})=2|E|-|V|$ for a cycle basis $\mathcal{B}$, then $G$ is planar. \end{lemma} \begin{proof} By theorems \ref{thm:equality=>fundamental} equality in equation (\ref{eq:lower-bound}) implies that $\mathcal{B}$ is minimal, elementary and fundamental. Thus there exists an ordering of $\mathcal{B}$ as described in lemma~\ref{lemma:fundamental}. By theorem~\ref{thm:equality=>fundamental} every cycle $C_i$ has exactly one edge in common with $C_1\cup\dots\cup C_{i-1}$. Thus by induction we can add the ``ear'' $P_i$ from $C_i$ into the planar drawing of $C_1\cup\dots\cup C_{i-1}$, for all $i\geq 2$. \end{proof} \begin{lemma}\label{lemma:hamiltonian+equality} Let $G(V,E)$ be a Hamiltonian graph. Then there exists a cycle basis $\mathcal{B}$ for which $\ell(\mathcal{B})=2|E|-|V|$ holds if and only if $G$ is outerplanar. \end{lemma} \begin{proof} By corollary~\ref{cor:length_outerplanar} a minimal cycle basis of an outerplanar graph has length $2|E|-|V|$. If equality holds in equ.(\ref{eq:lower-bound}) then $G$ is planar (lemma~\ref{lemma:2-connected+equality}) and $\mathcal{B}$ is fundamental (theorem~\ref{thm:equality=>fundamental}). Moreover $\mathcal{B}$ can be ordered such that every cycle $C_i$ has exactly one edge in common with $C_1\cup C_{i-1}$. Obviously $H_1=C_1$ is Hamiltonian cycle in $C_1$. Then by induction $H_{i+1}=H_{i}\oplus C_{i+1}$ is a Hamiltonian cycle in $C_1\cup C_{i+1}$. Furthermore we can draw the ``ears'' $P_{i+1}$ of the cycles $C_i$ (lemma~\ref{lemma:fundamental}) into the outside of $C_1\cup C_i$. Thus $H_i$ is the boundary to the exterior region of $G_i$ and the proposition follows by induction. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{figure}[htbp] \begin{center} \leavevmode \setlength{\unitlength}{0.13mm} \begin{picture}(423,310)(0,-10) \put(190,25){\blacken\ellipse{23}{23}} \put(30,145){\blacken\ellipse{23}{23}} \put(190,263){\blacken\ellipse{23}{23}} \put(270,145){\blacken\ellipse{23}{23}} \put(390,145){\blacken\ellipse{23}{23}} \path(190,265)(30,145)(190,25)(190,265)(270,145)(190,25)(390,145)(190,265) \put(200,280){\makebox(0,0)[lb]{$1$}} \put(0,165){\makebox(0,0)[lb]{$2$}} \put(200,0){\makebox(0,0)[lb]{$3$}} \put(230,135){\makebox(0,0)[lb]{$4$}} \put(405,160){\makebox(0,0)[lb]{$5$}} \end{picture} \caption{Non-Hamiltonian planar graph for which equality holds in lemma~\ref{lemma:2-connected+equality}.} \label{fig:nonhamilton} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The condition ``Hamiltonian'' in lemma~\ref{lemma:hamiltonian+equality} cannot be relaxed. An example of a planar (non-Hamiltonian) graph with $\ell(\mathcal{B})=2\,|E|-|V|$ is shown in figure~\ref{fig:nonhamilton}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %\bibliographystyle{abbrv} %\bibliography{cycle} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{10} \bibitem{Chartrand:67} G.~Chartrand and F.~Harary. \newblock Planar permutation graphs. \newblock {\em Ann.\ Inst.\ Henri Poincar{\`e} B}, 3:433--438, 1967. \bibitem{Chen:71} W.-K. Chen. \newblock On vector spaces associated with a graph. \newblock {\em SIAM J.\ Appl.\ Math.}, 20:525--529, 1971. \bibitem{Chickering:95} D.~M. Chickering, D.~Geiger, and D.~Heckerman. \newblock On finding a cycle basis of with a shortest maximal cycle. \newblock {\em Inform.\ Processing Let.}, 54:55--58, 1994. \bibitem{ColinVerdiere:90} Y.~{Colin de Verdi{\`e}re}. \newblock Sur un novel invariant des graphes et un crit{\`e}re de planarit{\'e}. \newblock {\em J.\ Comb.\ Theory B}, 50:11--21, 1990. \bibitem{Deo:82} N.~Deo, G.~M. Prabhu, and M.~S. Krishnamoorty. \newblock Algorithms for generating fundamental cycles in a graph. \newblock {\em ACM Trans.\ Math.\ Software}, 8:26--42, 1982. \bibitem{Dirac:60} G.~A. Dirac. \newblock {In abstrakten Graphen vorhandene vollst{\"a}ndige 4-Graphen und ihre Unterteilungen}. \newblock {\em Math.\ Nachr.}, 22:61--85, 1960. \bibitem{Downs:89a} G.~M. Downs, V.~J. Gillet, J.~D. Holliday, and M.~F. Lynch. \newblock Review of ring perception algorithms for chemical graphs. \newblock {\em J.\ Chem.\ Inf.\ Comput.\ Sci.}, 29:172--187, 1989. \bibitem{Freier:86} S.~M. Freier, R.~Kierzek, J.~A. Jaeger, N.~Sugimoto, M.~H. Caruthers, T.~Neilson, and D.~H. Turner. \newblock Improved free-energy parameters for predictions of {RNA} duplex stability. \newblock {\em Proc.\ Natl.\ Acad.\ Sci.\ (USA)}, 83:9373--9377, 1986. \bibitem{Hartvigsen:89} D.~Hartvigsen and E.~Zemel. \newblock Is every cycle basis fundamental? \newblock {\em J.\ Graph Theory}, 13:117--137, 1989. \bibitem{Horton:87} J.~D. Horton. \newblock A polynomial-time algorithm to find the shortest cycle basis of a graph. \newblock {\em SIAM J.\ Comput.}, 16:359--366, 1987. \bibitem{Kaveh:92} A.~Kaveh. \newblock {\em Structural Mechanics: Graph and Matrix Methods}. \newblock Research Studies Press, Exeter, UK, 1992. \bibitem{Kirchhoff:1847} G.~Kirchhoff. \newblock {\"U}ber die {A}ufl{\"o}sung der {G}leichungen, auf welche man bei der {U}ntersuchungen der linearen {V}erteilung galvanischer {S}tr{\"o}me gef{\"u}hrt wird. \newblock {\em Poggendorf Ann.\ Phys.\ Chem.}, 72:497--508, 1847. \bibitem{Plotkin:71} M.~Plotkin. \newblock Mathematical basis of ring-finding algorithms in {CIDS}. \newblock {\em J.\ Chem.\ Doc.}, 11:60--63, 1971. \bibitem{Thulasiraman:92} K.~Thulasiraman and M.~N.~S. Swamy. \newblock {\em Graphs: Theory and Algorithms}. \newblock J.\ Wiley \& Sons, New York, 1992. \bibitem{Vismara:97} P.~Vismara. \newblock Union of all the minimum cycle bases of a graph. \newblock {\em Electronic J.\ Comb.}, 4:\#R9 (15 pages), 1997. \bibitem{Voss:91} H.-J. Voss. \newblock {\em Cycles and Bridges in Graphs}. \newblock Kluwer, Dordrecht, 1991. \bibitem{Waterman:78a} M.~S. Waterman. \newblock Secondary structure of single-stranded nucleic acids. \newblock {\em Adv.\ Math.\ Suppl.\ Studies}, 1:167--212, 1978. \bibitem{Whitney:35} H.~Whitney. \newblock On abstract properties of linear dependence. \newblock {\em Am.\ J.\ Math.}, 57:509--533, 1935. \bibitem{Yan:95} L.~Yan. \newblock A family of special outerplanar graphs with only one triangle satisfying the cycle basis interpolation property. \newblock {\em Discr.\ Math.}, 143:293--297, 1995. \end{thebibliography} \end{document}