Deutsch Intern
Institute of Computer Science



Im Sommersemester 2019 findet auf Einladung von Prof. Dr. Alexander Wolff der folgende Vortrag statt:

Montag, 13. Mai 2019, 16.15 Uhr, Turing Hörsaal, Informatikgebäude, Am Hubland

Prof. Dr. Will Evans
Department of Computer Science
University of British Columbia
Vancouver, Canada


Contact Representations of Graphs in 3D


The talk focuses on contact representations of 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 show that for every 3-connected planar graph, there exists a simultaneous representation of the graph and its dual with 3D boxes. We give a linear-time algorithm for constructing such a representation. This result extends the existing primal-dual contact representations of planar graphs in 2D using circles and triangles. Our approach relies on a decomposition of the planar graph into three trees, called a Schnyder Wood.

While contact graphs in 2D are inherently planar, in 3D it is possible to represent non-planar graphs. We show how to represent optimal 1-planar graphs in 3D. A graph is 1-planar if there exists a drawing in the plane where each edge is crossed at most once, and an optimal n-vertex 1-planar graph has the maximum number of edges (4n-8). We describe a linear-time algorithm for representing optimal 1-planar graphs without separating 4-cycles with 3D boxes. However, not every optimal 1-planar graph admits a representation with boxes. Hence, we 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 graph with L-shaped polyhedra.