New Parameters for Beyond-Planar Graphs

DSpace Repository


Dokumentart: PhDThesis
Date: 2020-11-18
Source: Inhalte der Thesis basieren auf Resultaten aus den folgenden Veröffentlichungen: 1) P. Angelini, G. Da Lozzo, H. Förster, T. Schneck. 2-layer k-planar graphs: Density, crossing lemma, relationships, and pathwidth. Graph Drawing and Network Visualization GD 2020. Springer, Cham (to appear). 2) P. Angelini, M. A. Bekos, M. Kaufmann, T. Schneck. Efficient generation of different topological representations of graphs beyond-planarity. Journal of Graph Algorithms and Applications, 2020 (DOI: 10.7155/jgaa.00531). 3) P. Kindermann, T. Mchedlidze, T. Schneck, A. Symvonis. Drawing planar graphs with few segments on a polynomial grid. Graph Drawing and Network Visualization GD 2019, Seiten 416–429. Springer, Cham. 4) P. Angelini, M. A. Bekos, M. Kaufmann, T. Schneck. Low-degree graphs beyond planarity. Graph Drawing and Network Visualization GD 2018, Seiten 630–632. Springer, Cham.
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Informatik
Advisor: Kaufmann, Michael (Prof. Dr.)
Day of Oral Examination: 2020-10-19
DDC Classifikation: 004 - Data processing and computer science
Keywords: Graphenzeichnen , Algorithmus
Other Keywords:
Graph Drawing
Edge Density
Crossing Lemma
2-Layer Graphs
Complete Graphs
Complete Bipartite Graphs
Enumeration of Graphs
Bounded Vertex Degree
Order a printed copy: Print-on-Demand
Show full item record


Parameters for graphs appear frequently throughout the history of research in this field. They represent very important measures for the properties of graphs and graph drawings, and are often a main criterion for their classification and their aesthetic perception. In this direction, we provide new results for the following graph parameters: – The segment complexity of trees; – the membership of graphs of bounded vertex degree to certain graph classes; – the maximal complete and complete bipartite graphs contained in certain graph classes beyond-planarity; – the crossing number of graphs; – edge densities for outer-gap-planar graphs and for bipartite gap-planar graphs with certain properties; – edge densities and inclusion relationships for 2-layer graphs, as well as characterizations for complete bipartite graphs in the 2-layer setting.

This item appears in the following Collection(s)