On representing graphs by touching cuboids

David Bremner; William Evans; Fabrizio Frati; Laurie Heyer; Stephen G. Kobourov; William J. Lenhart; Giuseppe Liotta; David Rappaport; Sue H. Whitesides

doi:10.1007/978-3-642-36763-2_17

On representing graphs by touching cuboids

David Bremner, William Evans, Fabrizio Frati, Laurie Heyer, Stephen G. Kobourov, William J. Lenhart, Giuseppe Liotta, David Rappaport, Sue H. Whitesides

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Scopus citations

Abstract

We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids.

Original language	English (US)
Title of host publication	Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers
Pages	187-198
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-36763-2_17
State	Published - 2013
Event	20th International Symposium on Graph Drawing, GD 2012 - Redmond, WA, United States Duration: Sep 19 2012 → Sep 21 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7704 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	20th International Symposium on Graph Drawing, GD 2012
Country/Territory	United States
City	Redmond, WA
Period	9/19/12 → 9/21/12

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-36763-2_17

Cite this

Bremner, D., Evans, W., Frati, F., Heyer, L., Kobourov, S. G., Lenhart, W. J., Liotta, G., Rappaport, D., & Whitesides, S. H. (2013). On representing graphs by touching cuboids. In Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers (pp. 187-198). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS). https://doi.org/10.1007/978-3-642-36763-2_17

On representing graphs by touching cuboids. / Bremner, David; Evans, William; Frati, Fabrizio et al.
Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. 2013. p. 187-198 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7704 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bremner, D, Evans, W, Frati, F, Heyer, L, Kobourov, SG, Lenhart, WJ, Liotta, G, Rappaport, D & Whitesides, SH 2013, On representing graphs by touching cuboids. in Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7704 LNCS, pp. 187-198, 20th International Symposium on Graph Drawing, GD 2012, Redmond, WA, United States, 9/19/12. https://doi.org/10.1007/978-3-642-36763-2_17

Bremner D, Evans W, Frati F, Heyer L, Kobourov SG, Lenhart WJ et al. On representing graphs by touching cuboids. In Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers. 2013. p. 187-198. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-36763-2_17

@inproceedings{a5b6b126fbe34a0b8085939830c36bc0,

title = "On representing graphs by touching cuboids",

abstract = "We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids.",

author = "David Bremner and William Evans and Fabrizio Frati and Laurie Heyer and Kobourov, {Stephen G.} and Lenhart, {William J.} and Giuseppe Liotta and David Rappaport and Whitesides, {Sue H.}",

year = "2013",

doi = "10.1007/978-3-642-36763-2_17",

language = "English (US)",

isbn = "9783642367625",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "187--198",

booktitle = "Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers",

note = "20th International Symposium on Graph Drawing, GD 2012 ; Conference date: 19-09-2012 Through 21-09-2012",

}

TY - GEN

T1 - On representing graphs by touching cuboids

AU - Bremner, David

AU - Evans, William

AU - Frati, Fabrizio

AU - Heyer, Laurie

AU - Kobourov, Stephen G.

AU - Lenhart, William J.

AU - Liotta, Giuseppe

AU - Rappaport, David

AU - Whitesides, Sue H.

PY - 2013

Y1 - 2013

N2 - We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids.

AB - We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids.

UR - http://www.scopus.com/inward/record.url?scp=84874144058&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874144058&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36763-2_17

DO - 10.1007/978-3-642-36763-2_17

M3 - Conference contribution

AN - SCOPUS:84874144058

SN - 9783642367625

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 187

EP - 198

BT - Graph Drawing - 20th International Symposium, GD 2012, Revised Selected Papers

T2 - 20th International Symposium on Graph Drawing, GD 2012

Y2 - 19 September 2012 through 21 September 2012

ER -

On representing graphs by touching cuboids

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this