Space complexity: what makes planar graphs special?
Samir K. Datta, Raghav Kulkarni · Bulletin of the European Association for Theoretical Computer Science · 2013
The purpose of this article is to survey several useful properties of planar graphs that can be exploited specifically in the context of space bounded computation to obtain ecient algorithms. For completeness we also point out some situations where planar restrictions remain computationally as hard as general graphs.