Visibility Representations of Boxes in 2.5 Dimensions

Arleo, 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. 251-265(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_20).

Full text not available from this repository.

Abstract

We initiate the study of 2.5D box visibility representations (2.5D-BR) 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⩽19; (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-GBR) 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 Γ.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.999 Others
P Styles > P.900 Visibility
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1547

Actions (login required)

View Item View Item