  Let $G=(V(G), E(G))$ be an undirected graph with a measure function $\mu$
assigning non-negative values to subgraphs $H$ so that $\mu(H)$ does not exceed
the clique cover number of $H$. When $\mu$ satisfies some additional natural
conditions, we study the problem of separating $G$ into two subgraphs, each
with a measure of at most $2\mu(G)/3$ by removing a set of vertices that can be
covered with a small number of cliques $G$. When $E(G)=E(G_1)\cap E(G_2)$,
where $G_1=(V(G_1),E(G_1))$ is a graph with $V(G_1)=V(G)$, and $G_2=(V(G_2),
E(G_2))$ is a chordal graph with $V(G_2)=V(G)$, we prove that there is a
separator $S$ that can be covered with $O(\sqrt{l\mu(G)})$ cliques in $G$,
where $l=l(G,G_1)$ is a parameter similar to the bandwidth, which arises from
the linear orderings of cliques covers in $G_1$. The results and the methods
are then used to obtain exact and approximate algorithms which significantly
improve some of the past results for several well known NP-hard geometric
problems. In addition, the methods involve introducing new concepts and hence
may be of an independent interest.
