Visibility Representations of Boxes in 2.5 DimensionsArleo, Alessio and Binucci, Carla and Di Giacomo, Emilio and Evans, William S. and Grilli, Luca and Liotta, Giuseppe and Meijer, Henk and Montecchiani, Fabrizio and Whitesides, Sue and Wismath, Stephen (2016) Visibility Representations of Boxes in 2.5 Dimensions. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 251265(Official URL: http://dx.doi.org/10.1007/9783319501062_20). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_20
AbstractWe initiate the study of 2.5D box visibility representations (2.5DBR) 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 yaxis. We prove that: (i) Every complete bipartite graph admits a 2.5DBR; (ii) The complete graph Kn admits a 2.5DBR if and only if n⩽19; (iii) Every graph with pathwidth at most 7 admits a 2.5DBR, which can be computed in linear time. We then turn our attention to 2.5D grid box representations (2.5DGBR) which are 2.5DBRs such that the bottom face of every box is a unit square at integer coordinates. We show that an nvertex graph that admits a 2.5DGBR 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.5DGBR with a given footprint is NPcomplete. The footprint of a 2.5DBR Γ is the set of bottom faces of the boxes in Γ.
Actions (login required)
