Separators for Planar Graphs that are Almost Trees
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 TEXTWe 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