13.05.2019

Informatik-Kolloquium

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

Abstract:

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.

 

Homepage

http://www.cs.ubc.ca/~will/