𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the approximation of nonplanarity parameters for cubic graphs

✍ Scribed by Luerbio Faria; Celina M. Herrera de Figueiredo; Candido F.X. Mendonça

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
496 KB
Volume
141
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G = (V; E) be a simple graph. The NON-PLANAR DELETION problem consists in ÿnding a smallest subset E ⊂ E such that H =(V; E\E ) is a planar graph. The SPLITTING NUMBER problem consists in ÿnding the smallest integer k ¿ 0, such that a planar graph H can be deÿned from G by k vertex splitting operations. We establish the Max SNP-hardness of SPLITTING NUMBER and NON-PLANAR DELETION problems for cubic graphs.

📜 SIMILAR VOLUMES

The complexity of recognizing tough cubi
The complexity of recognizing tough cubic graphs
✍ D. Bauer; J. van den Heuvel; A. Morgana; E. Schmeichel 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 647 KB

We show that it is NP-hard to determine if a cubic graph G is l-tough. We then use this result to show that for any integer t > 1, it is NP-hard to determine if a 3 t-regular graph is t-tough. We conclude with some remarks concerning the complexity of recognizing certain subclasses of tough graphs.

On the Cubicity of Interval Graphs
On the Cubicity of Interval Graphs
✍ L. Sunil Chandran; Mathew C. Francis; Naveen Sivadasan 📂 Article 📅 2009 🏛 Springer Japan 🌐 English ⚖ 168 KB
On the Approximation of Finding A(nother
On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs
✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 144 KB

It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial-time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the co