Parameterized Complexity of Geometric Problems

Panos Giannopoulos, Christian Knauer, Sue Whitesides

The Computer Journal · 2007 · 26 citations · 34 references

Concepts

Abstract

This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and several other areas, together with an overview of the algorithmic techniques used. Fixed-parameter intractability results are surveyed as well. Finally, we give some directions for future research.

References

34