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.
The following conjecture already appears as open question in [Gav96].
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
-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].
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-
?