Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00130
NPcompleteness of the Planar Separator Problems
Vol. 10, no. 2, pp. 317328, 2006. Regular paper.
Abstract For a given graph G, the Separator Problem asks whether a
vertex or edge set of small cardinality (or weight) exists whose
removal partitions G into two disjoint graphs of approximately
equal sizes. Called the Vertex Separator Problem when the
removed set is a vertex set, and the Edge Separator Problem
when it is an edge set, both problems are NPcomplete for general
unweighted graphs [].
Despite the significance of planar graphs, it has not been known
whether the Planar Separator Problem, which considers a
planar graph and a threshold as an input, is NPcomplete or not.
In this paper, we prove that the Vertex Separator Problem is in
fact NPcomplete when G is a vertex weighted planar graph. The
Edge Separator Problem will be shown NPcomplete when G is a
vertex and edge weighted planar graph.
In addition, we consider how to treat the constant α ∈ R^{+} of the αSeparator Problem that partitions G
into two disjoint graphs of size at most ( 1− α) V(G) . The αSeparator Problem is not
NPcomplete for all real numbers α ∈ (0, 1/2 ],
because it would imply uncountably many Non Deterministic Turing
Machines. We will present a general scheme for treating a constant
in computer arithmetic, by introducing the notion of real
numbers comparable with rationals in polynomial time. This
approach allows us to prove NPcompleteness for each such real
number α.
