next up previous contents
Next: Treewidth Bounded Graphs Up: Specific Class of Graphs Previous: Chordal Rings   Contents


Planar Graphs

Let us recall that a plane graph is a planar graph embedded in the plane without any crossing edges. An outerplanar graph is a plane graph with all its nodes lying on one face (this includes trees).


\begin{theorem}[\cite{FJ88}]
Every plane graph $G$\ satisfies $\mbox{\rm SIRS}(...
...e, every outerplanar graph $G$\ verifies $\mbox{\rm SIRS}(G) = 1$.
\end{theorem}

Unfortunately the number of disjoint faces, p, can attain $\Theta(n)$. In [FJ88] the result is generalized for graph of genus $\gamma$ with an upper bound of $3p/2+\gamma$. Other results, but slightly weaker, are presented in the same article. No bound has been proved yet to be tight.


\begin{theorem}[\cite{GP96}]
For every integer $n$\ large enough there exists:
\...
...nded degree of compactness
$\Omega(\sqrt{n})$. \endsmall{itemize}
\end{theorem} 4

The following conjecture already appears as open question in [Gav96].


\begin{conjecture}
Every $n$-node planar graph has compactness $O(\sqrt{n})$.
\end{conjecture}


\begin{theorem}[\cite{TL97c}]
For every even integer $D \geqs 2$\ there exists ...
...D - 1$, for every $k \leqs
(n/38)^{1/2}$.
\par\endsmall{itemize}
\end{theorem}

The latter result uses a globe-graph (a subdivision of a complete bipartite graph K2,t) which is a series-parallel graph [Duf65], and also a graph of treewidth two [Bod92]. Thus the general $\Omega(\sqrt{n})$-lower bound for planar graphs holds also for the subclass of graphs of treewidth two (see Paragraph 3.5 for results about treewidth). The best known lower bound of compactness, regarding the multiplicative constant, for series-parallel graphs is:


\begin{theorem}[\cite{KRS97_tmp}]
\mbox{}
\beginsmall{itemize}
\item For every i...
...ernal and horizontal edges have been removed).
\endsmall{itemize}
\end{theorem}

Historically, the first $\Omega(\sqrt{n})$-lower bound for a series-parallel graph has been implicitly proved by [TL95]. The previous bound (using the same graph) was of $\Omega(n^{1/3})$ in [KKR93].

Open question 8    
- Are there constants k and c such that every planar graph G of diameter D satisfies k- $\mbox{\rm dilation}(G) \leqs 3D/2 + c$? or k- $\mbox{\rm stretch}(G) \leqs c$?

Actually [KRS97b] proposed a stronger version of Question 8: For every $\varepsilon >0$, is there a constant k such that every planar graph G of diameter D satisfies k- $\mbox{\rm dilation}(G) \leqs (1+\varepsilon)D$?


next up previous contents
Next: Treewidth Bounded Graphs Up: Specific Class of Graphs Previous: Chordal Rings   Contents

2000-03-21