Abstract: We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has Omega((m^2/n)log(m/n)) crossings. In d-dimensions, with d >= 4, this bound becomes Omega(m^2/n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^Theta(n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^Omega(n) lower bound and the n^O(n) upper bound.
Recommendations
Cites work
- scientific article; zbMATH DE number 1188564 (Why is no real title available?)
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 1241845 (Why is no real title available?)
- scientific article; zbMATH DE number 2145229 (Why is no real title available?)
- scientific article; zbMATH DE number 2159655 (Why is no real title available?)
- A Separator Theorem for Planar Graphs
- Bounded-degree graphs can have arbitrarily large slope numbers
- Bounded-degree graphs have arbitrarily large geometric thickness
- Bounded-degree graphs have arbitrarily large queue-number
- Counting Plane Graphs: Cross-Graph Charging Schemes
- Counting plane graphs: cross-graph charging schemes
- Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
- Counting triangulations of planar point sets
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Crossing-Free Subgraphs
- Distinct distances in graph drawings
- Expansion in SL₂( R) and monotone expanders
- Extremal problems in discrete geometry
- Graphs with E Edges Have Pagenumber O(√E)
- Improved bounds for planar k-sets and related problems
- Improving the crossing lemma by finding more crossings in sparse graphs
- Layout of Graphs with Bounded Tree-Width
- On the Number of Crossing‐Free Matchings, Cycles, and Partitions
- On the Queue Number of Planar Graphs
- On topological graphs with at most four crossings per edge
- Space crossing numbers
- Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
- The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
- Three-dimensional graph drawing
- Upward three-dimensional grid drawings of graphs
Cited in
(7)
This page was built for publication: Crossings in grid drawings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405129)
