✦ LIBER ✦

Chordal Completions of Planar Graphs

✍ Scribed by F.R.K. Chung; D. Mumford

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 431 KB
Volume: 62
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1056

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

More than one tough chordal planar graph

More than one tough chordal planar graphs are Hamiltonian

✍ B�hme, Thomas; Harant, Jochen; Tk�?, Michal 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB 👁 3 views

We prove the result stated in the title. Furthermore, it is proved that for any > 0, there is a 1-tough chordal planar graph G such that the length of a longest cycle of G is less than |V (G )|.

A generalization of chordal graphs

✍ P. D. Seymour; R. W. Weaver 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 487 KB

In a 3-connected planar triangulation, every circuit of length 2 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are "separated" by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In t

Vertex partitions of chordal graphs

✍ David R. Wood 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A __k‐tree__ is a chordal graph with no (__k__ + 2)‐clique. An ℓ‐__tree‐partition__ of a graph __G__ is a vertex partition of __G__ into ‘bags,’ such that contracting each bag to a single vertex gives an ℓ‐tree (after deleting loops and replacing parallel edges by a single edge). We pro

Diameters of iterated clique graphs of c

Diameters of iterated clique graphs of chordal graphs

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB

## Abstract The clique graph __K__(__G__) of a graph is the intersection graph of maximal cliques of __G.__ The iterated clique graph __K__^__n__^(__G__) is inductively defined as __K__(K^n−1^(__G__)) and __K__^1^(__G__) = __K__(__G__). Let the diameter diam(__G__) be the greatest distance between

On the tree representation of chordal gr

On the tree representation of chordal graphs

✍ Yukio Shibata 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB 👁 1 views

On the interval number of a chordal grap

On the interval number of a chordal graph

✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum