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 ?
In second place, Yamasaki et al., [30] deal with a special kind of query graph where no vertex is totally surrounded by edges, called outerplanar graph pattern.
The next lemma makes use of the following property of outerplanar graphs. If G = (V,E) is an outerplanar graph, then |E|[less than or equal to]2|V|-3.
Moreover, G is an outerplanar graph. It is well known that every outerplanar graph has a vertex of degree at most 2.
Proof: Let [member of] be an outerplanar graph. We shall show that for every maximal biconnected component H of [member of] and a vertex u in it, there exists a c-p-BOX(1)-realization of H in which u is safe.
Proof: Let G be an outerplanar graph. We shall show that for every maximal biconnected component H of G and a vertex u in it, there exists a c-p-BOX(1)-realization of H in which u is safe.
Theorem 3.2 Let [d.sub.k] be the limit probability that a vertex of a connected outerplanar graph has degree k then
A dissection is a biconnected outerplanar graph. All these graphs are well-known and well-studied combinatorial objects [FS05, DFLS04, FN99], which have plenty of applications in physics, computer science, and bioinformatics (see e.g.
The "dual" construction is also possible: given any undirected tree whose all internal vertices have degree three, one can obtain a maximal outerplanar graph by embedding the tree in the plane, collapsing all the leaves into a single vertex, obtaining a plane multigraph, and taking the planar dual of this multigraph (Bondy and Murty, 1976, Sec.
Theorem 1.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].sub.0](G) [greater than or equal to] 7.
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.
Wang, "Adjacent vertex distinguishing total colorings of outerplanar graphs," Journal of Combinatorial Optimization, vol.