piwik-script

Intern
    Institut für Informatik

    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

    www.cs.ubc.ca/~will/

    Hinweis zum Datenschutz

    Mit 'OK' verlassen Sie die Seiten der Universität Würzburg und werden zu Facebook weitergeleitet. Informationen zu den dort erfassten Daten und deren Verarbeitung finden Sie in deren Datenschutzerklärung.

    Hinweis zum Datenschutz

    Mit 'OK' verlassen Sie die Seiten der Universität Würzburg und werden zu Twitter weitergeleitet. Informationen zu den dort erfassten Daten und deren Verarbeitung finden Sie in deren Datenschutzerklärung.

    Kontakt

    Institut für Informatik
    Am Hubland
    97074 Würzburg

    E-Mail

    Suche Ansprechpartner

    Hubland Süd
    Hubland Süd
    Hubland Nord