Representation Complexities of SemiAlgebraic Graphs
From MaRDI portal
Publication:5237912
DOI10.1137/18M1221606zbMath1425.05100arXiv1709.08259OpenAlexW2978125219WikidataQ127184066 ScholiaQ127184066MaRDI QIDQ5237912
Publication date: 25 October 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1709.08259
Hypergraphs (05C65) Graph representations (geometric and intersection representations, etc.) (05C62) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)
Cites Work
- Unnamed Item
- Unnamed Item
- Bisector energy and few distinct distances
- An incidence theorem in higher dimensions
- On the Erdős distinct distances problem in the plane
- Zarankiewicz's problem for semi-algebraic hypergraphs
- Extremal problems in discrete geometry
- Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
- Can visibility graphs be represented compactly?
- On counting point-hyperplane incidences
- Clique partitions, graph compression and speeding-up algorithms
- Efficient algorithms for approximating polygonal chains
- Cutting algebraic curves into pseudo-segments and applications
- A semi-algebraic version of Zarankiewicz's problem
- Lower bounds for incidences with hypersurfaces
- A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing
- Ramsey-type results for semi-algebraic relations
- Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
- On the Number of Incidences Between Points and Curves
- Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances
- On the number of cells defined by a family of polynomials on a variety
- Density and regularity theorems for semi-algebraic hypergraphs
- Incidences of not-too-degenerate hyperplanes
- On Range Searching with Semialgebraic Sets. II
- On the Betti Numbers of Real Varieties
- On a problem of K. Zarankiewicz
This page was built for publication: Representation Complexities of SemiAlgebraic Graphs
