Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949895 | Discrete Applied Mathematics | 2017 | 8 Pages |
Abstract
A unit disk graph is a c-strip graph if it has a unit disk representation in which all centers of the unit disks lie between two parallel lines at distance c. The classes of c-strip graphs for various c are studied in the literature. For example, the 0-strip graphs are exactly the unit interval graphs, and every 3/2-strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their properties. A graph is a thin strip graph if it is a c-strip graph for every c>0. We show that there is no constant t such that the t-strip graphs are exactly the thin strip graphs. We also show that the class of thin strip graphs properly includes the class of mixed unit interval graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Takashi Hayashi, Akitoshi Kawamura, Yota Otachi, Hidehiro Shinohara, Koichi Yamazaki,