On grids in topological graphs

DOI10.1016/J.COMGEO.2014.02.003MaRDI QIDQ2249043zbMATH OpenOpenAlexFDO

Authors Eyal Ackerman, Jacob Fox, János Pach, Andrew Suk

Publication date 27 June 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2014.02.003

zbMATH Keywords

geometric graphstopological graphsTurán-type problems

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• On grids in topological graphs
• Topological graphs with no large grids
• Combinatorial Geometry and Graph Theory
• Disjoint edges in topological graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges

Cites work

• A bipartite strengthening of the crossing Lemma
• A separator theorem for string graphs and its applications
• A Turán-type theorem on chords of a convex polygon
• Applications of the crossing number
• Approximation schemes for covering and packing problems in image processing and VLSI
• Bounds for generalized thrackles
• Coloring axis-parallel rectangles
• Crossing number, pair-crossing number, and expansion
• Crossing Stars in Topological Graphs
• Disjoint edges in topological graphs
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Graph theory with applications
• Label placement by maximum independent set in rectangles
• Note on geometric graphs
• Some geometric applications of Dilworth's theorem
• String graphs and incomparability graphs
• The Clarkson–Shor Technique Revisited and Extended
• Topological graphs with no large grids
• Toward a theory of crossing numbers

Cited in

(19)

• On fan-crossing and fan-crossing free graphs
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• The density of fan-planar graphs
• On fan-crossing graphs
• A survey of grid diagrams and a proof of Alexander's theorem
• Topological graphs with no large grids
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• Constructing \(\gamma\)-sets of grids
• On disjoint crossing families in geometric graphs
• On the Size of Planarly Connected Crossing Graphs
• k-quasi-planar graphs
• Tangled thrackles
• Quantitative restrictions on crossing patterns
• On convex geometric graphs with no \(k+1\) pairwise disjoint edges
• On grids in topological graphs
• Straight-line drawings of 1-planar graphs
• On optimal beyond-planar graphs
• A structure theorem for pseudosegments and its applications

This page was built for publication: On grids in topological graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249043)