Name
Abstract | ||
|---|---|---|
Let G=(V,E) be a simple graph. The NON-PLANAR DELETION problem consists in finding a smallest subset E' ⊂ E such that H=(V,E\E') is a planar graph. The SPLITTING NUMBER problem consists in finding the smallest integer k ≥ 0, such that a planar graph H can be defined fromG by k vertex splitting operations. We establish the Max SNP-hardness of SPLITTING NUMBER and NON-PLANAR DELETION problems for cubic graphs. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/S0166-218X(03)00370-6 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
computational difficulty of problems,smallest subset e,maximum planar subgraph,cubic graph,smallest integer k,splitting number,planar graph h,nonplanarity parameter,planar graph,simple graph,topological graph theory,complexity classes,non-planar deletion problem,splitting number problem,k vertex splitting operation,complexity class,graph theory | Discrete mathematics,Combinatorics,Outerplanar graph,Cubic graph,Polyhedral graph,Book embedding,Symmetric graph,1-planar graph,Planar graph,Mathematics,Pancyclic graph | Journal |
Volume | Issue | ISSN |
141 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
6 | 0.66 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luerbio Faria | 1 | 133 | 20.98 |
| Celina M. Herrera de Figueiredo | 2 | 22 | 2.40 |
| Candido F.X. Mendonça | 3 | 12 | 2.52 |