𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chordal embeddings of planar graphs

✍ Scribed by V. Bouchitté; F. Mazoit; I. Todinca

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
361 KB
Volume
273
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Robertson and Seymour conjectured that the treewidth of a planar graph and the treewidth of its geometric dual di er by at most one. Lapoire solved the conjecture in the a rmative, using algebraic techniques. We give here a much shorter proof of this result.

📜 SIMILAR VOLUMES

Chordal Completions of Planar Graphs
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.

Enumeration of projective-planar embeddi
Enumeration of projective-planar embeddings of graphs
✍ Seiya Negami 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 562 KB

It will be shown that the number of equivalence classes of embeddings of a 3-connected nonplanar graph into a projective plane coincides with the number of isomorphism classes of planar double coverings of the graph and a combinatorial method to determine the number will be developed.

On convex embeddings of planar 3-connect
On convex embeddings of planar 3-connected graphs
✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi

Unique and faithful embeddings of projec
Unique and faithful embeddings of projective-planar graphs
✍ Seiya Negami 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

A graph G is uniquelyembeddable in a surface f 2 if for any two embeddings f,,f2 : G + f 2 , there exists an isomorphism u : G + G and a homeo- admits an embedding f : G + F2 such that for any isomorphism (T : G + G, there is a homeomorphism h : F 2 f 2 with h . f = f . u. It will be shown that if

Circular embeddings of planar graphs in
Circular embeddings of planar graphs in nonspherical surfaces
✍ R.B. Richter; P.D. Seymour; J. Širáň 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 506 KB

We show that every 3-connected planar graph has a circular embedding in some nonspherical surface. More generally, we characterize those planar graphs that have a 2-representative embedding in some nonspherical surface. This is proved in Section 3. Standard results in the theory show that it suffic