TR-186: Reduced Constants for Simple Cycle Graph Separation

Abstract

If G is an n vertex maximal planar graph, then the vertex set of G can be partitioned into three sets A, B, C such that neither A nor 8 contains more than (1-B)n vertices for any B:::;1 /3, no edge from G connects a vertex in A to a vertex in 8, and C is a cycle in G containing no more than (✓ 2B+✓ 2-2B)✓n+0(1) vertices. Specifically, when B=1/3, the separator C is of size (✓ 2/3+✓ 4/3)”n+0(1 ), which is roughly 1.971197✓n. The constant 1.971197 is an improvement over the best known so far result of Miller 2✓ 2 = 2.828427. If non­negative weights adding to at most 1 are associated with the vertices of G, then the vertex set of G can be partitioned into three sets A, 8, C such that neither A nor B has weight exceeding 1-B, no edge from G connects a vertex in A to a vertex in 8, and C is a simple cycle with no more than 2✓n+0(1) vertices.