Veröffentlichung

Titel:

Saturated simple and 2-simple topological graphs with few edges

AutorInnen:

Péter Hajnal
Alexander Igamberdiev
Günter Rote
André Schulz

Kategorie:

Artikel in Zeitschriften

erschienen in:

J. Graph Algorithms Appl., Vol. 22, No. 1, 2018, pp. 117--138

Abstract:

A simple topological graph is a topological graph in which any two edges have at most one common point, which is either their common endpoint or a proper crossing. More generally, in a k-simple topological graph, every pair of edges has at most k common points of this kind. We construct saturated simple and 2-simple graphs with few edges. These are k-simple graphs in which no further edge can be added. We improve the previous upper bounds of Kynčl, Pach, Radoičić, and Tóth [Comput. Geom., 48, 2015] and show that there are saturated simple graphs on n vertices with only 7n edges and saturated 2-simple graphs on n vertices with 14.5n edges. As a consequence, 14.5n edges is also a new upper bound for k-simple graphs (considering all values of k). We also construct saturated simple and 2-simple graphs that have some vertices with low degree.

Download:

Springer

BibTeX-Eintrag:

@article{DBLP:journals/jgaa/HajnalIRS18, author = {P{\'{e}}ter Hajnal and Alexander Igamberdiev and G{\"{u}}nter Rote and Andr{\'{e}} Schulz}, title = {Saturated simple and 2-simple topological graphs with few edges}, journal = {J. Graph Algorithms Appl.}, volume = {22}, number = {1}, pages = {117--138}, year = {2018} }