Saturated Simple and 2-simple Topological Graphs with Few Edges
From MaRDI portal
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 Kynv{c}l, Pach, Radoiv{c}i'c, and T'oth 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.
Recommendations
- Saturated simple and 2-simple topological graphs with few edges
- Saturated simple and \(k\)-simple topological graphs
- Saturated graphs with minimal number of edges
- Graph Drawing
- On edges crossing few other edges in simple topological complete graphs
- On simple totally complemented-edged graphs
- Saturated graphs of prescribed minimum degree
- Cycle-saturated graphs with minimum number of edges
- Enumeration of simple complete topological graphs
- Enumeration of simple complete topological graphs
Cites work
Cited in
(2)
This page was built for publication: Saturated Simple and 2-simple Topological Graphs with Few Edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827825)
