@inproceedings{d272c0d08fbc4927a6e852f8ecd0b7bc,
title = "Better approximation schemes for disk graphs",
abstract = "We consider Maximum Independent Set and Minimum Vertex Cover on disk graphs. We propose an asymptotic FPTAS for Minimum Vertex Cover on disk graphs of bounded ply. This scheme can be extended to an EPTAS on arbitrary disk graphs, improving on the previously known PTAS [8]. We introduce the notion of level density for disk graphs, which is a generalization of the notion of ply. We give an asymptotic FPTAS for Maximum Independent Set on disk graphs of bounded level density, which is also a PTAS on arbitrary disk graphs. The schemes are a geometric generalization of Baker{\textquoteright}s EPTASs for planar graphs [3].",
author = "{Leeuwen, van}, E.J.",
year = "2006",
doi = "10.1007/11785293_30",
language = "English",
isbn = "3-540-35753-X",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "316--327",
editor = "L. Arge and R. Freivalds",
booktitle = "Algorithm Theory - SWAT 2006 : 10th Scandinavian Workshop, Riga, Latvia, July 6-8, 2006 : proceedings",
address = "Germany",
}