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- ?