2023-03-29T20:41:19Z
https://oa.upm.es/cgi/oai2
oai:oa.upm.es:4948
2016-04-20T13:57:39Z
7374617475733D707562
7375626A656374733D6D6174656D617469636173
747970653D636F6E666572656E63655F6974656D
Cover Contact Graphs.
Atienza, Nieves
Castro, Natalia de
Cortés, Carmen
Garrido, M. Ángeles
Grima, Clara I.
Hernández Peñalver, Gregorio
Márquez, Alberto
Moreno, Auxiliadora
Nöllenburg, Martin
Portillo, José Ramon
Reyes, Pedro
Valenzuela, Jesús
Villar, Maria Trinidad
Wolff, Alexander
Mathematics
We study problems that arise in the context of covering certain geometric objects (so-called seeds, e.g., points or disks) by a set of other geometric objects (a so-called cover, e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pair wise disjoint, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). We are interested in two types of tasks: (a) deciding whether a given seed set has a connected CCG, and (b) deciding whether a given graph has a realization as a CCG on a given seed set. Concerning task (a) we give efficient algorithms for the case that seeds are points and covers are disks or triangles. We show that the problem becomes NP-hard if seeds and covers are disks. Concerning task (b) we show that it is even NP-hard for point seeds and disk covers (given a fixed correspondence between vertices and seeds).
Facultad de Informática (UPM)
https://creativecommons.org/licenses/by-nc-nd/3.0/es/
2008
info:eu-repo/semantics/conferenceObject
Presentation at Congress or Conference
Graph Drawing. Proceedings of the 15th International Symposium on Graph Drawing, GD 2007 | 15th International Symposium on Graph Drawing, GD 2007 | 23/09/2007-26/09/2007 | Sydney, Australia
PeerReviewed
application/pdf
eng
http://www.cs.usyd.edu.au/~visual/gd2007/
info:eu-repo/semantics/openAccess
https://oa.upm.es/4948/