In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.

p-BOX: A new graph model / M. Soto Gomez, C.T. Caro. - In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. - ISSN 1462-7264. - 17:1(2015), pp. 169-186.

p-BOX: A new graph model

M. Soto Gomez;
2015

Abstract

In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.
(max-)tolerance graphs; Boxicity 2 graphs; Disk graphs; Graph representation; Graph theory; Intersection graphs
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
2015
Article (author)
File in questo prodotto:
File Dimensione Formato  
06_2015_pBox_a_new_graph_class.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 354.96 kB
Formato Adobe PDF
354.96 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/961423
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 14
social impact