Presentation 2017-11-16
[Invited Talk] On the Recognition of Unit Grid Intersection Graphs
Satoshi Tayu, Shuichi Ueno,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) We show that the recognition problem for unit grid intersection graphs is NP-complete.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Grid graphsNP-completeRecognition problemUnit grid intersection graphs
Paper # CAS2017-44,MSS2017-28
Date of Issue 2017-11-09 (CAS, MSS)

Conference Information
Committee CAS / MSS / IPSJ-AL
Conference Date 2017/11/16(2days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair Mitsuru Hiraki(Renesas) / Morikazu Nakamura(Univ. of Ryukyus) / Takashi Horiyama(Saitama University)
Vice Chair Hideaki Okazaki(Shonan Inst. of Tech.) / Shigemasa Takai(Osaka Univ.)
Secretary Hideaki Okazaki(Renesas) / Shigemasa Takai(Shonan Inst. of Tech.) / (Toshiba)
Assistant Yohei Nakamura(Hitachi) / Hideki Kinjo(Okinawa Univ.)

Paper Information
Registration To Technical Committee on Circuits and Systems / Technical Committee on Mathematical Systems Science and its applications / Special Interest Group on Algorithms
Language ENG
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) [Invited Talk] On the Recognition of Unit Grid Intersection Graphs
Sub Title (in English)
Keyword(1) Grid graphsNP-completeRecognition problemUnit grid intersection graphs
1st Author's Name Satoshi Tayu
1st Author's Affiliation Tokyo Institute of Technology(Tokyo Inst. of Tech.)
2nd Author's Name Shuichi Ueno
2nd Author's Affiliation Tokyo Institute of Technology(Tokyo Inst. of Tech.)
Date 2017-11-16
Paper # CAS2017-44,MSS2017-28
Volume (vol) vol.117
Number (no) CAS-300,MSS-301
Page pp.pp.15-20(CAS), pp.15-20(MSS),
#Pages 6
Date of Issue 2017-11-09 (CAS, MSS)