English Intern
Lehrstuhl für Informatik I - Algorithmen und Komplexität

Vortrag von Giuseppe Liotta


Am Montag (20. März) hält Giuseppe Liotta von der Universität Perugia einen Vortrag zum Thema "1-Planarity". Der Vortrag findet im Raum E39 statt und beginnt um 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.