Deutsch Intern
    Chair of Computer Science I - Algorithms, Complexity, and Knowledge-Based Systems

    Talk by Giuseppe Liotta

    03/20/2017

    On Monday (March 20), Giuseppe Liotta of the University of Perugia gives a talk on "1-Planarity". The talk will take place in room E39 at 16:00.

    Abstract:

    A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. Among the various families of beyond planar graphs recently investigated in the  literature, the 1-planar graphs are among the most popular ones. I first briefly recall the main results concerning both the density of 1-planar graphs and the complexity of recognizing 1-planar graphs. 

    After this introduction, I shall review the main results concerning geometric representations of 1-planar graphs. Namely, I will describe some results and proof techniques for straight-line drawings and 1-bend drawings with right-angle crossings and with few edge slopes. I will then consider visibility representations of 1-planar graphs. In particular, some recent results and proof techniques concerning bar 1-visibility representations, rectangle visibility representations, and ortho-polygon visibility representations will be recalled. 

    https://arxiv.org/abs/1703.02261

    Back

    Contact

    Lehrstuhl für Informatik I (Effiziente Algorithmen und wissensbasierte Systeme)
    Am Hubland
    97074 Würzburg

    Phone: +49 931 31-85054
    Email

    Find Contact

    Hubland Süd, Geb. Z8 Hubland Süd, Geb. M2