✦ LIBER ✦

-constructibility of planar graphs

✍ Scribed by C. M. Mynhardt; I. Broere

Publisher: John Wiley and Sons
Year: 1980
Tongue: English
Weight: 386 KB
Volume: 4
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190040304

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper, the concept of the 𝒢‐constructibility of graphs is introduced and investigated with particular reference to planar graphs. It is conjectured that the planar graphs are minimally N‐constructible, where N is a finite set of graphs and an infinite set 𝒢 is obtained such that the planar graphs are also minimally 𝒢‐constructible. Finally, some properties of the set of all N‐constructible graphs are discussed and compared with the corresponding properties of planar graphs.

📜 SIMILAR VOLUMES

Monotone drawings of planar graphs

✍ János Pach; Géza Tóth 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

## Abstract Let __G__ be a graph drawn in the plane so that its edges are represented by __x__‐monotone curves, any pair of which cross an even number of times. We show that __G__ can be redrawn in such a way that the __x__‐coordinates of the vertices remain unchanged and the edges become non‐cross

Domination numbers of planar graphs

✍ MacGillivray, G.; Seyffarth, K. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 967 KB

The problem of determining the domination number of a graph is a well known NPhard problem, even when restricted to planar graphs. By adding a further restriction on the diameter of the graph, we prove that planar graphs with diameter two and three have bounded domination numbers. This implies that

Chordal Completions of Planar Graphs

✍ F.R.K. Chung; D. Mumford 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 431 KB

We prove that every planar graph on \(n\) vertices is contained in a chordal graph with at most \(c n \log n\) edges for some abolsute constant \(c\) and this is best possible to within a constant factor. 1994 Academic Press, Inc.

Outerplanar Partitions of Planar Graphs

✍ Kiran S. Kedlaya 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 254 KB

An outerplanar graph is one that can be embedded in the plane so that all of the vertices lie on one of the faces. We investigate a conjecture of Chartrand, Geller, and Hedetniemi, that every planar graph can be edge-partitioned into two outerplanar subgraphs. We refute the stronger statement that e

On planar hypohamiltonian graphs

✍ Gábor Wiener; Makoto Araya 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for eve

Posets and planar graphs

✍ Stefan Felsner; William T. Trotter 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract Usually __dimension__ should be an integer valued parameter. We introduce a refined version of dimension for graphs, which can assume a value [__t__ − 1 ↕ __t__], thought to be between __t__ − 1 and __t__. We have the following two results: (a) a graph is outerplanar if and only if its