TY - GEN
T1 - 3D proportional contact representations of graphs
AU - Alam, Md Jawaherul
AU - Kobourov, Stephen G.
AU - Liotta, Giuseppe
AU - Pupyrev, Sergey
AU - Veeramoni, Sankar
PY - 2014
Y1 - 2014
N2 - In 3D contact representations, the vertices of a graph are represented by 3D polyhedra and the edges are realized by non-zero-area common boundaries between corresponding polyhedra. While contact representations with cuboids have been studied in the literature, we consider a novel generalization of the problem in which vertices are represented by axis-aligned polyhedra that are union of two cuboids. In particular, we study the weighted (proportional) version of the problem, where the volumes of the polyhedra and the areas of the common boundaries realize prespecified vertex and edge weights. For some classes of graphs (e.g., outerplanar, planar bipartite, planar, complete), we provide algorithms to construct such representations for arbitrary given weights.We also show that not all graphs can be represented in 3D with axis-aligned polyhedra of constant complexity.
AB - In 3D contact representations, the vertices of a graph are represented by 3D polyhedra and the edges are realized by non-zero-area common boundaries between corresponding polyhedra. While contact representations with cuboids have been studied in the literature, we consider a novel generalization of the problem in which vertices are represented by axis-aligned polyhedra that are union of two cuboids. In particular, we study the weighted (proportional) version of the problem, where the volumes of the polyhedra and the areas of the common boundaries realize prespecified vertex and edge weights. For some classes of graphs (e.g., outerplanar, planar bipartite, planar, complete), we provide algorithms to construct such representations for arbitrary given weights.We also show that not all graphs can be represented in 3D with axis-aligned polyhedra of constant complexity.
UR - http://www.scopus.com/inward/record.url?scp=84906748772&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906748772&partnerID=8YFLogxK
U2 - 10.1109/IISA.2014.6878773
DO - 10.1109/IISA.2014.6878773
M3 - Conference contribution
AN - SCOPUS:84906748772
SN - 9781479961719
T3 - IISA 2014 - 5th International Conference on Information, Intelligence, Systems and Applications
SP - 27
EP - 32
BT - IISA 2014 - 5th International Conference on Information, Intelligence, Systems and Applications
PB - IEEE Computer Society
T2 - 5th International Conference on Information, Intelligence, Systems and Applications, IISA 2014
Y2 - 7 July 2014 through 9 July 2014
ER -