On the complexity of recognizing intersection and touching graphs of disks
| العنوان: | On the complexity of recognizing intersection and touching graphs of disks |
|---|---|
| المؤلفون: | Heinz Breu, David G. Kirkpatrick |
| المصدر: | Graph Drawing ISBN: 9783540607236 Graph Drawing |
| بيانات النشر: | Springer Berlin Heidelberg, 1996. |
| سنة النشر: | 1996 |
| مصطلحات موضوعية: | Discrete mathematics, Trapezoid graph, 1-planar graph, Metric dimension, Combinatorics, Indifference graph, Pathwidth, Intersection, Chordal graph, Data_FILES, Permutation graph, Astrophysics::Earth and Planetary Astrophysics, Astrophysics::Galaxy Astrophysics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics |
| الوصف: | Disk intersection (respectively, touching) graphs are the intersection graphs of closed disks in the plane whose interiors may (respectively, may not) overlap. In a previous paper [BK93], we showed that the recognition problem for unit disk intersection graphs (i.e. intersection graphs of unit disks) is NP-hard. That proof is easily modified to apply to unit disk touching graphs as well. In this paper, we show how to generalize our earlier construction to accomodate disks whose size may differ. In particular, we prove that the recognition problems for both bounded-ratio disk intersection graphs and bounded-ratio disk touching graphs are also NP-hard. (By bounded-ratio we refer to the natural generalization of the unit constraint in which the radius ratio of the largest to smallest permissible disk is bounded by some fixed constant.) The latter result contrasts with the fact that the disk touching graphs (of unconstrained ratio) are precisely the planar graphs, and are hence polynomial time recognizable. The recognition problem for disk intersection graphs (of unconstrained ratio) has recently been shown to be NP-hard as well [Kra95]. |
| ردمك: | 978-3-540-60723-6 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::c167227ad3c4567177217ae429e49448 https://doi.org/10.1007/bfb0021793 |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi...........c167227ad3c4567177217ae429e49448 |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783540607236 |
|---|