TY - GEN
T1 - Contact representations of graphs in 3D
AU - Alam, Jawaherul
AU - Evans, William
AU - Kobourov, Stephen
AU - Pupyrev, Sergey
AU - Toeniskoetter, Jackson
AU - Ueckerdt, Torsten
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - We study contact representations of non-planar graphs in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra. We present a liner-time algorithm constructing a representation of a 3-connected planar graph, its dual, and the vertex-face incidence graph with 3D boxes. We then investigate contact representations of 1- planar graphs. We first prove that optimal 1-planar graphs without separating 4-cycles admit a contact representation with 3D boxes. However, since not every optimal 1-planar graph can be represented in this way, we also consider contact representations with the next simplest axis-aligned 3D object, L-shaped polyhedra. We provide a quadratic-time algorithm for representing optimal 1-planar graphs with L-shapes.
AB - We study contact representations of non-planar graphs in which vertices are represented by axis-aligned polyhedra in 3D and edges are realized by non-zero area common boundaries between corresponding polyhedra. We present a liner-time algorithm constructing a representation of a 3-connected planar graph, its dual, and the vertex-face incidence graph with 3D boxes. We then investigate contact representations of 1- planar graphs. We first prove that optimal 1-planar graphs without separating 4-cycles admit a contact representation with 3D boxes. However, since not every optimal 1-planar graph can be represented in this way, we also consider contact representations with the next simplest axis-aligned 3D object, L-shaped polyhedra. We provide a quadratic-time algorithm for representing optimal 1-planar graphs with L-shapes.
UR - http://www.scopus.com/inward/record.url?scp=84951816003&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84951816003&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21840-3_2
DO - 10.1007/978-3-319-21840-3_2
M3 - Conference contribution
AN - SCOPUS:84951816003
SN - 9783319218397
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 14
EP - 27
BT - Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
A2 - Dehne, Frank
A2 - Sack, Jorg-Rudiger
A2 - Stege, Ulrike
PB - Springer-Verlag
T2 - 14th International Symposium on Algorithms and Data Structures, WADS 2015
Y2 - 5 August 2015 through 7 August 2015
ER -