Geometric Thickness of Complete Graphs
From MaRDI portal
Abstract: We define the geometric thickness of a graph to be the smallest number of layers such that we can draw the graph in the plane with straight-line edges and assign each edge to a layer so that no two edges on the same layer cross. The geometric thickness lies between two previously studied quantities, the (graph-theoretical) thickness and the book thickness. We investigate the geometric thickness of the family of complete graphs, K_n. We show that the geometric thickness of K_n lies between ceiling((n/5.646) + 0.342) and ceiling(n/4), and we give exact values of the geometric thickness of K_n for n <= 12 and n in {15,16}. We also consider the geometric thickness of the family of complete bipartite graphs. In particular, we show that, unlike the case of complete graphs, there are complete bipartite graphs with arbitrarily large numbers of vertices for which the geometric thickness coincides with the standard graph-theoretical thickness.
Recommendations
Cited in
(43)- Geometric thickness in a grid
- Thickness and outerthickness for embedded graphs
- Geometric biplane graphs. I: Maximal graphs
- Graph treewidth and geometric thickness parameters
- Graph drawings with few slopes
- \(\mathsf{NIC}\)-planar graphs
- Extension of a theorem of Whitney
- Partitions of complete geometric graphs into plane trees
- A simulated annealing algorithm for determining the thickness of a graph
- Bounded-degree graphs have arbitrarily large geometric thickness
- Packing plane spanning trees and paths in complete geometric graphs
- Fan-crossing free graphs and their relationship to other beyond-planar graphs
- Thickness and colorability of geometric graphs
- Maximizing the degree of (geometric) thickness-t regular graphs
- Drawing Cubic Graphs with the Four Basic Slopes
- Geometric Thickness in a Grid of Linear Area
- Proximity drawings of high-degree trees
- Layouts of Expander Graphs
- Cubic Graphs Have Bounded Slope Parameter
- scientific article; zbMATH DE number 4077286 (Why is no real title available?)
- Relating graph thickness to planar layers and bend complexity
- Relating graph thickness to planar layers and bend complexity
- Thickness and Antithickness of Graphs
- scientific article; zbMATH DE number 2145231 (Why is no real title available?)
- Angular Resolutions: Around Vertices and Crossings
- Ideal spatial graph configurations
- The geometric thickness of low degree graphs
- Thickness and connectivity in graphs
- Graph Drawing
- Straight-line drawings of 1-planar graphs
- Fold thickness of some classes of graphs
- On graph thickness, geometric thickness, and separator theorems
- Geometric thickness of multigraphs is \(\exists \mathbb{R} \)-complete
- On the biplanarity of blowups
- Thickness and colorability of geometric graphs
- Partitioning complete geometric graphs on dense point sets into plane subgraphs
- Geometric thickness of multigraphs is \(\exists \mathbb{R}\)-complete
- Some properties of k-Delaunay and k-Gabriel graphs
- Partitioning complete geometric graphs on dense point sets into plane subgraphs
- Bounds on the crossing resolution of complete geometric graphs
- On simultaneous planar graph embeddings
- On \(k\)-planar crossing numbers
- Simultaneous graph embedding with bends and circular arcs
This page was built for publication: Geometric Thickness of Complete Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4511256)
