Citation
Frk. Chung et D. Mumford, CHORDAL COMPLETIONS OF PLANAR GRAPHS, J COMB TH B, 62(1), 1994, pp. 96-106
Citations number
18
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
62
Issue
1
Year of publication
1994
Pages
96 - 106
Database
ISI
SICI code
0095-8956(1994)62:1<96:CCOPG>2.0.ZU;2-S
Abstract
We prove that every planar graph on n vertices is contained in a chord
al graph with at most cn log n edges for some abolsute constant c and
this is best possible to within a constant factor. (C) 1994 Academic P
ress, Inc.