# Optimization and approximation on systems of geometric by van Leeuwen E. By van Leeuwen E.

Similar geometry and topology books

Plane Geometry and its Groups

San Francisco 1967 Holden-Day. octavo. , 288pp. , index, hardcover. superb in VG DJ, a couple of small closed tears.

Additional info for Optimization and approximation on systems of geometric objects

Sample text

Chapter 4 Geometric Intersection Graphs and Their Representation As is clear from the previous chapter, a fundamental problem for most classes of geometric intersection graphs is how to recognize such graphs. The recognition problem is often NP-hard and in PSPACE, but membership of NP is not always known. One way of proving membership of NP is to find a representation of the graph that uses polynomially many bits (polynomial in the number of vertices of the graph). This is a polynomial representation.

An object s is said to be scaled around a point p by τ > 0 if (assuming s is the only object in the space) s is translated by −p, the space is scaled by τ , and then s is translated by p. Scaling an object around a point gives more control over the scaling, which is needed in the following definition. 2 An object s is scalable if there is a point p ∈ int(s) such that for any τ ∈ R>0 \{1}, scaling s around p by τ gives an object s for which cl(s) ⊆ int(s ) or cl(s ) ⊆ int(s). If s is scalable, fix such a point p and call it the scaling point of s, denoted by cs .

Not every graph is a string graph) [241, 242, 98]. A relatively recent overview of the results in this area and a description of further classes can be found in the course notes of Kratochv´ıl . 2 Intersection Graphs of Higher Dimensional Objects Another way to generalize interval graphs, more in line with further topics of this thesis, is to consider d-dimensional objects that are intervals if d = 1. A good example are intersection graphs of d-dimensional axis-parallel boxes. g. [a1 , b1 ] × · · · × [ad , bd ] for numbers ai < bi .