Crossings in grid drawings

zbMATH Open1300.05191arXiv1301.0303MaRDI QIDQ405129FDOQ405129

Adam Sheffer, Vida Dujmović, Pat Morin

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1301.0303

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Graph Drawing
• Graphs drawn with few crossings per edge
• A bipartite strengthening of the crossing Lemma
• The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
• Bounds for Convex Crossing Numbers

zbMATH Keywords

graph drawinggrid drawing

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• A Separator Theorem for Planar Graphs
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Extremal problems in discrete geometry
• Improving the crossing lemma by finding more crossings in sparse graphs
• Improved bounds for planar \(k\)-sets and related problems
• Counting Plane Graphs: Flippability and Its Applications
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Crossing-Free Subgraphs
• Counting triangulations of planar point sets
• Layout of Graphs with Bounded Tree-Width
• On the Queue Number of Planar Graphs
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Title not available (Why is that?)
• Counting Plane Graphs: Cross-Graph Charging Schemes
• Bounded-degree graphs have arbitrarily large geometric thickness
• Bounded-degree graphs can have arbitrarily large slope numbers
• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• Title not available (Why is that?)
• Distinct distances in graph drawings
• On topological graphs with at most four crossings per edge
• Upward three-dimensional grid drawings of graphs
• Space crossing numbers
• Title not available (Why is that?)
• Graphs with E Edges Have Pagenumber O(√E)
• Title not available (Why is that?)
• Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
• The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
• Counting Plane Graphs: Cross-Graph Charging Schemes
• Title not available (Why is that?)
• Three-dimensional graph drawing

Cited In (7)

• Layered separators in minor-closed graph classes with applications
• Planar Crossovers
• Removing even crossings
• Layouts of Expander Graphs
• Title not available (Why is that?)
• Crossing patterns of segments
• Block Crossings in Storyline Visualizations

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)