Abstract Let $$n \in \mathbb {N}$$ n ∈ N and $$k \in \mathbb {N}_0$$ k ∈ N 0 . Given a set P of n points in the plane, a pair $$\{p,q\}$$ { p , q } of points in P is called k-deep, if there are at least k points from P strictly on each side of the line spanned by p and q. A k-deep clique is a subset of P with all its pairs k-deep. We show that if P is in general position (i.e., no three points on a line), there is a k-deep clique of size at least $$ \max \{1,\lfloor \frac{n}{k+1} \rfloor \}$$ max { 1 , ⌊ n k + 1 ⌋ } ; this is tight, for example in convex position. A k-deep clique in any set P of n points cannot have size exceeding $$n-\lceil \frac{3k}{2} \rceil $$ n - ⌈ 3 k 2 ⌉ ; this is tight for $$k \le \frac{n}{3}$$ k ≤ n 3 . Moreover, for $$k \le \lfloor \frac{n}{2} \rfloor - 1$$ k ≤ ⌊ n 2 ⌋ - 1 , a k-deep clique cannot have size exceeding $$2\sqrt{n(\lfloor \frac{n}{2} \rfloor -k)}$$ 2 n ( ⌊ n 2 ⌋ - k ) ; this is tight within a constant factor. We also pay special attention to $$(\frac{n}{2}-1)$$ ( n 2 - 1 ) -deep cliques (for n even), which are called halving cliques. These have been considered in the literature by Khovanova and Yang, 2012, and they play a role in the latter bound above. Every set P in general position with a halving clique Q of size m must have at least $$\lfloor \frac{(m-1)(m+3)}{2}\rfloor $$ ⌊ ( m - 1 ) ( m + 3 ) 2 ⌋ points. If Q is in convex position, the set P must have size at least $$m(m-1)$$ m ( m - 1 ) . This is tight, i.e., there are sets $$Q_m$$ Q m of m points in convex position which can be extended to a set of $$m(m-1)$$ m ( m - 1 )

Let d be a positive integer. Can a given graph G be realized in R^d so that vertices are mapped to distinct points, two vertices being adjacent if and only if the corresponding points lie on a common line that is parallel to some axis? Graphs admitting such realizations have been studied in the literature for decades under different names. Peterson asked in [Discrete Appl. Math., 2003] about the complexity of the recognition problem. While the two-dimensional case corresponds to the class of line graphs of bipartite graphs and is well-understood, the complexity question has remained open for all higher dimensions. In this paper, we answer this question. We establish the NP-completeness of the recognition problem for any fixed dimension, even in the class of bipartite graphs. To do this, we strengthen a characterization of induced subgraphs of 3-dimensional Hamming graphs due to Klavžar and Peterin. We complement the hardness result by showing that for some important classes of perfect graphs –including chordal graphs and distance-hereditary graphs– the minimum dimension of the Euclidean space in which the graph can be realized, or the impossibility of doing so, can be determined in linear time.

We consider requests for capacity in a given tree network T = ( V , E ) where each edge e of the tree has some integer capacity u e . Each request f is a node pair with an integer demand d f and a profit w f which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and b -matching problems. When all demands are 1, we have the integer multicommodity flow problem. Garg et al. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. We then consider the problem with arbitrary demands. When the maximum demand d max is at most the minimum edge capacity u min , we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed.