# Approximation algorithms for NP-complete problems on planar graphs

@article{Baker1983ApproximationAF, title={Approximation algorithms for NP-complete problems on planar graphs}, author={Brenda S. Baker}, journal={24th Annual Symposium on Foundations of Computer Science (sfcs 1983)}, year={1983}, pages={265-273} }

This paper describes a general technique that can be used to obtain approximation algorithms for various NP-complete problems on planar graphs. The strategy depends on decomposing a planar graph into subgraphs of a form we call k- outerplanar. For fixed k, the problems of interest are solvable optimally in linear time on k-outerplanar graphs by dynamic programming. For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each… Expand

#### Figures and Topics from this paper

#### 960 Citations

Computational Study on a PTAS for Planar Dominating Set Problem

- Mathematics, Computer Science
- Algorithms
- 2013

It is shown that the approximation ratio achieved by the mentioned application of the framework is not bounded by any constant for the planar dominating set problem. Expand

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs

- Mathematics, Computer Science
- STACS
- 2013

This paper develops an algorithm running in O(2^{O((k log k)^{2/3})}n) time and polynomial space, where k is the size of the Steiner tree and n is the number of vertices of the graph. Expand

NC Algorithms for Partitioning Planar Graphs into Induced Forests and Approximating NP-Hard Problems

- Mathematics, Computer Science
- WG
- 1995

An optimal NC algorithm for computing a partition of the vertex set of a given K4-free or K2, 3-free graph into two subsets each of which induces a forest is designed. Expand

Approximation Schemes for Planar Graph Problems

- Computer Science
- Encyclopedia of Algorithms
- 2008

Many NP-hard graph problems become easier to approximate on planar graphs and their generalizations when the problem admits a polynomial-time approximation scheme (PTAS): a collection of (1 + )-approximation algorithms for all > 0. Expand

A Near-Optimal Planarization Algorithm

- Computer Science, Mathematics
- SODA
- 2014

A dynamic programming algorithm for Weighted Vertex Planarization on graphs of treewidth w with running time 2O(w log w) · n, thereby improving over previous double-exponential algorithms. Expand

Approximation Schemes for Planar Graph Problems

- Mathematics
- 2008

Many NP-hard graph problems become easier to approximate on planar graphs and their 11 generalizations. (A graph is planar if it can be drawn in the plane (or the sphere) without crossings. 12 For… Expand

Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2005

It is demonstrated that the tree decomposition-based approach provides a valuable way of exactly solving VERTEX COVER on planar graphs, and the impressive power of the so-called Nemhauser/Trotter theorem is demonstrated which provides a VERTex COVER-specific, extremely useful data reduction through polynomial time preprocessing. Expand

Computational study on planar dominating set problem

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2009

Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with n… Expand

An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs

- Mathematics, Computer Science
- Discuss. Math. Graph Theory
- 2019

Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, an efficient polynomial time approximation scheme (EPTAS) is presented for the V C P3problem on planar graphs. Expand

Computational study for domination problems in planar graphs

- Computer Science
- 2012

This work develops efficient implementations of algorithms for computing optimal branch-decompositions of planar graphs and proves a better upper bound for the branchwidth in terms of the minimum size of CDS. Expand

#### References

SHOWING 1-10 OF 32 REFERENCES

An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs

- Mathematics, Computer Science
- SIAM J. Comput.
- 1982

This paper presents a polynomial-time approximation algorithm for the maximum independent set problem on planar graphs, and finds an independent set that is necessarily larger in size than half a maximumIndependent set. Expand

Planar Embedding of Planar Graphs

- Mathematics
- 1983

Abstract : Planar embedding with minimal area of graphs on an integer grid is an interesting problem in VLSI (Very Large Scale Integrated) theory. Valiant gave an algorithm to construct a planar… Expand

On linear area embedding of planar graphs

- Mathematics
- 1981

Planar embedding with minimal area of graphs on an integer grid is one of the major issues in VLSI. Valiant [1981] gave an algorithm to construct a planar embedding for trees in linear area; he also… Expand

Linear-time computability of combinatorial problems on series-parallel graphs

- Mathematics, Computer Science
- JACM
- 1982

It is shown in a umfied manner that there exist hnearume algorithms for many combinatorial problems ff an input graph is restricted to the class of series-parallel graphs. Expand

On the Problem of Partitioning Planar Graphs

- Mathematics
- 1982

The results in this paper are closely related to the effective use of the divide-and-conquer strategy for solving problems on planar graphs. It is shown that every planar graph can be partitioned… Expand

A Separator Theorem for Planar Graphs

- Mathematics
- 1977

Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more… Expand

Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

- Mathematics, Computer Science
- SIAM J. Comput.
- 1972

This paper presents ways for constructing efficient algorithms for finding a minimum coloring, a minimum covering by cliques, a maximum clique, and a maximum independent set given a chordal graph. Expand

Worst-case ration for planar graphs and the method of induction on faces

- Computer Science
- 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981)
- 1981

A fanlily of results concerning certain extrenlal properties of planar graphs is presented and the greedy heuristic applied to a planar graph with n nodes yields an independent set of size at least 4n/21 times the optimum. Expand

On approximating a vertex cover for planar graphs

- Mathematics, Computer Science
- STOC '82
- 1982

The approximation problem for vertex cover of n-vertex planar graphs is treated and two results are presented: a linear time approximation algorithm and an O(n log n) time approximation scheme. Expand

Edge Dominating Sets in Graphs

- Mathematics
- 1980

We prove that the edge dominating set problem for graphs is $NP$-complete even when restricted to planar or bipartite graphs of maximum degree 3. We show as a corollary that the minimum maximal… Expand