View Related Documents

Abstract

We study intersection graphs of segments with prescribed slopes in the plane. A sufficient and necessary condition on tuples of slopes in order to define the same class of graphs is presented for both the possibilities that the parallel segments can or cannot overlap. Classes of intersection graphs of segments with four slopes are fully described; in particular, we find an infinite set of quadruples of slopes which define mutually distinct classes of intersection graphs of segments with those slopes.
Supported in part by KONTAKT ME337/99
This research was supported by GAUK 158/99 and GAČR 201/99/0242. Institute for Theoretical Computer Science (ITI) is supported as project LN00A056 by the Ministry of Education of Czech Republic.

Fulltext Preview

Image of the first page of the fulltext document