Separating hyperplanes of edge polytopes

Let G be a finite connected simple graph with d vertices and let P G ⊂ R d be the edge polytope of G. We call P G decomposable if P G decomposes into integral polytopes P G + and P G − via a hyperplane. In this paper, we explore various aspects of decomposition of P G : we give an algorithm deciding the decomposability of P G , we prove that P G is normal if and only if both P G + and P G − are normal, and we also study how a condition on the toric ideal of P G (namely, the ideal being generated by quadratic binomials) behaves under decomposition.