Crossings in grid drawings

zbMath1300.05191arXiv1301.0303MaRDI QIDQ405129

Adam Sheffer, Vida Dujmović, Pat Morin

Publication date: 4 September 2014

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

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

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)

Related Items (2)

Layered separators in minor-closed graph classes with applications ⋮ Layouts of Expander Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• Counting triangulations of planar point sets
• Three-dimensional graph drawing
• Extremal problems in discrete geometry
• Improving the crossing lemma by finding more crossings in sparse graphs
• Distinct distances in graph drawings
• Improved bounds for planar \(k\)-sets and related problems
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• On topological graphs with at most four crossings per edge
• Upward three-dimensional grid drawings of graphs
• Bounded-degree graphs have arbitrarily large geometric thickness
• Bounded-degree graphs can have arbitrarily large slope numbers
• Counting Plane Graphs: Flippability and Its Applications
• Space Crossing Numbers
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• A Separator Theorem for Planar Graphs
• Crossing-Free Subgraphs
• Graphs with E Edges Have Pagenumber O(√E)
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• 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
• Layout of Graphs with Bounded Tree-Width
• Counting Plane Graphs: Cross-Graph Charging Schemes
• On the Queue Number of Planar Graphs

This page was built for publication: Crossings in grid drawings