Abstract
This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1+δ can be achieved in O(n 2) time for any given constant δ > 0, no matter whether each vertex of G is given a weight or not. In case G is given without a map, a ratio of 4 can be achieved in O(n 7) time if no vertex is given a weight, while a ratio of O(log n) can be achieved in O(n 7 log n) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41 (1994) 153–180.
H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25 (1996) 1305–1317.
O.V. Borodin. Cyclic coloring of plane graphs. Discrete Math. 100 (1992) 281–289.
Z.-Z. Chen. Efficient approximation schemes for maximization problems on K3,3-free or K5-free graphs. J. Algorithms 26 (1998) 166–187.
Z.-Z. Chen, M. Grigni, and C.H. Papadimitriou. Planar map graphs. STOC’98, 514–523. See http://rnc2.r.dendai.ac.jp/~chen/papers/mg2.ps.gz for a full version.
J. Hästad. Clique is hard to approximate within n1-∈. STOC’96, 627–636.
R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979) 177–189.
R.J. Lipton and R.E. Tarjan. Applications of a planar separator theorem. SIAM J. Computing 9 (1980) 615–627.
O. Ore and M.D. Plummer. Cyclic coloration of plane graphs. Recent Progress in Combinatorics, pp. 287–293, Academic Press, 1969.
M. Thorup. Map graphs in polynomial time. FOCS’98, 396–405.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, ZZ. (2000). Approximation Algorithms for Independent Sets in Map Graphs. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_11
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive