Visibility representations are a well-known paradigm to represent graphs. From a high-level perspective, a visibility representation of a graph G maps the vertices of G to non-overlapping geometric objects and the edges of G to visibilities, i.e., segments that do not intersect any geometric object other than at their end-points. In this paper, we initiate the study of 2.5D box visibility representations (2.5D-BRs) where vertices are mapped to 3D boxes having the bottom face in the plane z=0 and edges are unobstructed lines of sight parallel to the x- or y-axis. We prove that: (i) Every complete bipartite graph admits a 2.5D-BR; (ii) The complete graph Kn admits a 2.5D-BR if and only if n<=18; (iii) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBRs), which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n-vertex graph that admits a 2.5D-GBR has at most 4n-6 √n edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete (the footprint of a 2.5D-BR Γ is the set of bottom faces of the boxes in Γ).

### Visibility representations of boxes in 2.5 dimensions

#### Abstract

Visibility representations are a well-known paradigm to represent graphs. From a high-level perspective, a visibility representation of a graph G maps the vertices of G to non-overlapping geometric objects and the edges of G to visibilities, i.e., segments that do not intersect any geometric object other than at their end-points. In this paper, we initiate the study of 2.5D box visibility representations (2.5D-BRs) where vertices are mapped to 3D boxes having the bottom face in the plane z=0 and edges are unobstructed lines of sight parallel to the x- or y-axis. We prove that: (i) Every complete bipartite graph admits a 2.5D-BR; (ii) The complete graph Kn admits a 2.5D-BR if and only if n<=18; (iii) Every graph with pathwidth at most 7 admits a 2.5D-BR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5D-GBRs), which are 2.5D-BRs such that the bottom face of every box is a unit square at integer coordinates. We show that an n-vertex graph that admits a 2.5D-GBR has at most 4n-6 √n edges and this bound is tight. Finally, we prove that deciding whether a given graph G admits a 2.5D-GBR with a given footprint is NP-complete (the footprint of a 2.5D-BR Γ is the set of bottom faces of the boxes in Γ).
##### Scheda breve Scheda completa Scheda completa (DC)
2018
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11391/1428691`
• ND
• 6
• 3