planar graph

(redirected from Outerplanar graph)

planar graph

[′plā·nər ‚graf]
(mathematics)
A graph that can be drawn in a plane without any lines crossing.
References in periodicals archive ?
30] deal with a special kind of query graph where no vertex is totally surrounded by edges, called outerplanar graph pattern.
Since each page admits an outerplanar graph, G can be decomposed into p outerplanar graphs.
It is well known that every outerplanar graph has a vertex of degree at most 2.
Therefore, for any outerplanar graph there exists an ordering of its vertices in which the edges do not cross.
k] be the limit probability that a vertex of a connected outerplanar graph has degree k then
Let H be a maximal outerplanar graph (no edge can be added without violating outerplanarity); then it is immediate that the boundary of the exterior face of H is a Hamiltonian cycle C and each interior face is triangular (Harary, 1972, p.
11 For all i [greater than or equal to] 4, there exists an outerplanar graph G without cycles of lengths 4 to i such that [[chi].
However, Astratian and Oksimets [2] showed that LT graphs that are not maximal outerplanar (maximal outerplanar graphs are hamiltonian) have size at least 2n - 2.
Kierstead, "The relaxed game chromatic number of outerplanar graphs," Journal of Graph Theory, 46 (2004) 69-78.
In this particular case, we provide constructive representations for interval, block and outerplanar graphs.
This paradigm was used successfully in calculating the genus distributions of 3-regular outerplanar graphs [Gr11b], of 4-regular outerplanar graphs [PKG11], of Halin graphs [Gr13], and of the 3 x n-mesh graphs [KPG12].
Part (a) and Part (b) have been proved for outerplanar graphs [15], and graphs with [DELTA] [greater than or equal to] 12 which can be embedded in a surface of nonnegative characteristic [2].