** 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).

Unfortunately the number of disjoint faces, *p*, can attain
.
In [FJ88] the result is generalized for graph of
genus
with an upper bound of .
Other results,
but slightly weaker, are presented in the same article. No bound has
been proved yet to be tight.

^{4}

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

The latter result uses a *globe-graph* (a subdivision of a
complete bipartite graph *K*_{2,t}) which is a series-parallel
graph [Duf65], and also a graph of treewidth two [Bod92].
Thus the general
-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:

Historically, the first
-lower bound for a
series-parallel graph has been implicitly proved by [TL95]. The
previous bound (using the same graph) was of
in [KKR93].

**Open question 8**
*
*

- Are there constants *k* and *c* such that every planar graph *G*
of diameter *D* satisfies *k*-
? or
*k*-
?*
*
Actually [KRS97b] proposed a stronger version of
Question 8: For every
,
is there a
constant *k* such that every planar graph *G* of diameter *D*
satisfies *k*-
?

** Next:** Treewidth Bounded Graphs
** Up:** Specific Class of Graphs
** Previous:** Chordal Rings
** Contents**

*2000-03-21*