| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2014-04-24 10:20 Thin strip graphs Yota Otachi (JAIST), Akitoshi Kawamura (Univ. of Tokyo), Hidehiro Shinohara (Tohoku Univ.), Takashi Hayashi, Koichi Yamazaki (Gunma Univ.)  COMP2014-1 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | A unit disk graph is a emph{$c$-strip graph} if it has a unit disk representation in which all centers of the unit disks lie in a parallel strip of width $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 any $sqrt{3}/2$-strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their property. A graph is a emph{thin strip graph} if it is a $c$-strip graph for any $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 contains a proper superclass of the class of unit interval graphs, which is called the emph{mixed unit interval graphs}. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | Unit disk graph / Thin strip graph / Mixed unit interval graph / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 114, no. 19, COMP2014-1, pp. 1-4, April 2014. | |
| Paper # | COMP2014-1 | |
| Date of Issue | 2014-04-17 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2014-1 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2014-04-24 - 2014-04-24 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Tohoku University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2014-04-COMP |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Thin strip graphs |
| Sub Title (in English) | |
| Keyword(1) | Unit disk graph |
| Keyword(2) | Thin strip graph |
| Keyword(3) | Mixed unit interval graph |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Yota Otachi |
| 1st Author's Affiliation | Japan Advanced Institute of Science and Technology (JAIST) |
| 2nd Author's Name | Akitoshi Kawamura |
| 2nd Author's Affiliation | University of Tokyo (Univ. of Tokyo) |
| 3rd Author's Name | Hidehiro Shinohara |
| 3rd Author's Affiliation | Tohoku University (Tohoku Univ.) |
| 4th Author's Name | Takashi Hayashi |
| 4th Author's Affiliation | Gunma University (Gunma Univ.) |
| 5th Author's Name | Koichi Yamazaki |
| 5th Author's Affiliation | Gunma University (Gunma Univ.) |
| Speaker | Author-3 |
| Date Time | 2014-04-24 10:20:00 |
| Presentation Time | 35 minutes |
| Registration for | COMP |
| Paper # | COMP2014-1 |
| Volume (vol) | vol.114 |
| Number (no) | no.19 |
| Page | pp.1-4 |
| #Pages | 4 |
| Date of Issue | 2014-04-17 (COMP) |
[Return to Top Page]