Convex Polygon Intersection Graphs

Van Leeuwen, Erik and Van Leeuwen, Jan (2011) Convex Polygon Intersection Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 377-388(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_35).

Full text not available from this repository.

Abstract

Geometric intersection graphs are graphs determined by intersections of geometric objects. We study the complexity of visualizing the arrangements of objects that induce such graphs. We give a general framework for describing geometric intersection graphs, using arbitrary finite base sets of rationally given convex polygons and affine transformations. We prove that for every class of intersection graphs that fits the framework, the graphs in the class have a representation using polynomially many bits. Consequently, the recognition problem of these classes is in NP (and thus NP-complete). We also give an algorithm to find a drawing of the objects in the plane, if a graph class fits the framework.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_35
Classifications: G Algorithms and Complexity > G.560 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1223

Actions (login required)

View Item View Item