A new separation theorem with geometric applications

Farhad Shahrokhi

paper

A new separation theorem with geometric applications

arXiv:1504.04938

Abstract

Let $G = (V (G), E (G))$ be an undirected graph with a measure function $μ$ assigning non-negative values to subgraphs $H$ so that $μ (H)$ does not exceed the clique cover number of $H$ . When $μ$ satisfies some additional natural conditions, we study the problem of separating $G$ into two subgraphs, each with a measure of at most $2 μ (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 (l μ (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.

Proceedings of EuroCG 2010, Dortmund, Germany, March 22-24, 2010

A new separation theorem with geometric applications

Abstract

Cited by in corpus (2)