Deutsch Intern
Chair of Computer Science I - Algorithms and Complexity

Talk by Giuseppe Liotta


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.


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.