Separators for Planar Graphs that are Almost Trees

08/08/2018
by   Linda Cai, et al.
0

We prove that a connected planar graph with n vertices and n+μ edges has a vertex separator of size O( √(μ) + 1), and this separator can be computed in linear time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset