On the public citation graph
Some provably hard crossing number problems
0 signed · 95 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/cpa.3160380606openalex-snapshot
Polynomial realization of pseudoline arrangements
inferredcites →https://doi.org/10.1002/jgt.3190120306openalex-snapshot
Rectilinear drawings of graphs
inferredcites →https://doi.org/10.1007/bf01166556openalex-snapshot
Teilungen der Ebene durch Geraden oder topologische Geraden
inferredcites →https://doi.org/10.1007/bf02187696openalex-snapshot
Upper bounds for configurations and polytopes inR d
inferredcites →https://doi.org/10.1007/bfb0082792openalex-snapshot
The universality theorems on the classification problem of configuration varieties and convex polytopes varieties
inferredcites →https://doi.org/10.1016/0012-365x(80)90096-5openalex-snapshot
Proof of a conjecture of Burr, Grünbaum, and Sloane
inferredcites →https://doi.org/10.1016/0097-3165(80)90038-2openalex-snapshot
Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
inferredcites →https://doi.org/10.1016/0097-3165(84)90050-5openalex-snapshot
Semispaces of configurations, cell complexes of arrangements
inferredcites →https://doi.org/10.1016/s0021-9800(70)80007-2openalex-snapshot
Toward a theory of crossing numbers
inferredcites →https://doi.org/10.1080/00029890.1973.11993230openalex-snapshot
Crossing Number Problems
inferredcites →https://doi.org/10.1090/s0273-0979-1986-15415-7openalex-snapshot
There are asymptotically far fewer polytopes than we thought
inferredcites →https://doi.org/10.1145/73007.73046openalex-snapshot
Coordinate representation of order types requires exponential storage
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/jgt.22027openalex-snapshot
On the Pseudolinear Crossing Number
inferred← citeshttps://doi.org/10.1002/jgt.3190160502openalex-snapshot
New results on rectilinear crossing numbers and plane embeddings
inferred← citeshttps://doi.org/10.1002/jgt.3190170308openalex-snapshot
Bounds for rectilinear crossing numbers
inferred← citeshttps://doi.org/10.1006/jctb.2000.1978openalex-snapshot
Which Crossing Number Is It Anyway?
inferred← citeshttps://doi.org/10.1007/978-1-4614-0110-0_24openalex-snapshot
Realizability of Graphs and Linkages
inferred← citeshttps://doi.org/10.1007/978-3-030-04414-5_18openalex-snapshot
Crossing Numbers and Stress of Random Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-04414-5_28openalex-snapshot
The Complexity of Drawing a Graph in a Polygonal Region
inferred← citeshttps://doi.org/10.1007/978-3-030-35802-0_6openalex-snapshot
Crossing Numbers of Beyond-Planar Graphs
inferred← citeshttps://doi.org/10.1007/978-3-031-49272-3_13openalex-snapshot
On the Complexity of Lombardi Graph Drawing
inferred← citeshttps://doi.org/10.1007/978-3-032-10503-5_4openalex-snapshot
Intersection Graphs of Segments and $$\exists \mathbb {R} $$
inferred← citeshttps://doi.org/10.1007/978-3-032-10503-5_5openalex-snapshot
The Existential Theory of the Reals as a Complexity Class: A Compendium
inferred← citeshttps://doi.org/10.1007/978-3-319-42634-1_37openalex-snapshot
Approximating the Maximum Rectilinear Crossing Number
inferred← citeshttps://doi.org/10.1007/978-3-319-50106-2_32openalex-snapshot
Approximating the Rectilinear Crossing Number
inferred← citeshttps://doi.org/10.1007/978-3-319-62127-2_23openalex-snapshot
The Complexity of Drawing Graphs on Few Lines and Few Planes
inferred← citeshttps://doi.org/10.1007/978-3-319-91908-9_6openalex-snapshot
10 Reasons to Get Interested in Graph Drawing
inferred← citeshttps://doi.org/10.1007/978-3-540-24595-7_2openalex-snapshot
An Experimental Study of Crossing Minimization Heuristics
inferred← citeshttps://doi.org/10.1007/978-3-540-77537-9_28openalex-snapshot
Simultaneous Geometric Graph Embeddings
inferred← citeshttps://doi.org/10.1007/978-3-642-03456-5_21openalex-snapshot
The Crossing Number of Graphs: Theory and Computation
inferred← citeshttps://doi.org/10.1007/978-3-642-11805-0_32openalex-snapshot
Complexity of Some Geometric and Topological Problems
inferred← citeshttps://doi.org/10.1007/978-3-642-21515-5_63openalex-snapshot
A Solution to Bipartite Drawing Problem Using Genetic Algorithm
inferred← citeshttps://doi.org/10.1007/s00224-015-9662-0openalex-snapshot
Fixed Points, Nash Equilibria, and the Existential Theory of the Reals
inferred← citeshttps://doi.org/10.1007/s00224-017-9800-yopenalex-snapshot
The Complexity of Tensor Rank
inferred← citeshttps://doi.org/10.1007/s00224-023-10151-xopenalex-snapshot
Beyond the Existential Theory of the Reals
inferred← citeshttps://doi.org/10.1007/s00453-019-00653-xopenalex-snapshot
Crossing Number for Graphs with Bounded Pathwidth
inferred← citeshttps://doi.org/10.1007/s00454-016-9831-1openalex-snapshot
Recognition and Complexity of Point Visibility Graphs
inferred← citeshttps://doi.org/10.1007/s00454-023-00540-xopenalex-snapshot
Topological Art in Simple Galleries
inferred← citeshttps://doi.org/10.1007/s00454-025-00783-wopenalex-snapshot
An Algorithm for Estimating the Crossing Number of Dense Graphs, and Continuous Analogs of the Crossing and Rectilinear Crossing Numbers
inferred← citeshttps://doi.org/10.1007/s00607-005-0133-3openalex-snapshot
On the Crossing Number of Complete Graphs
inferred← citeshttps://doi.org/10.1007/s10208-023-09610-1openalex-snapshot
Further $$\exists {\mathbb {R}}$$-Complete Problems with PSD Matrix Factorizations
inferred← citeshttps://doi.org/10.1016/j.comgeo.2019.04.003openalex-snapshot
Approximating the rectilinear crossing number
inferred← citeshttps://doi.org/10.1016/j.cosrev.2022.100490openalex-snapshot
Parameterized analysis and crossing minimization problems
inferred← citeshttps://doi.org/10.1016/j.dam.2018.03.070openalex-snapshot
The crossing number of locally twisted cubes LTQn
inferred← citeshttps://doi.org/10.1016/j.jcss.2020.10.006openalex-snapshot
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
inferred← citeshttps://doi.org/10.1016/j.jctb.2012.09.004openalex-snapshot
Integer realizations of disk and segment graphs
inferred← citeshttps://doi.org/10.1016/s0012-365x(02)00491-0openalex-snapshot
Toward the rectilinear crossing number of Kn: new drawings, upper bounds, and asymptotics
inferred← citeshttps://doi.org/10.1016/s0012-365x(99)00201-0openalex-snapshot
On a matching problem in the plane
inferred← citeshttps://doi.org/10.1080/00207169408804322openalex-snapshot
Genetic algorithms for drawing bipartite graphs
inferred← citeshttps://doi.org/10.1090/s0894-0347-1990-1046181-2openalex-snapshot
The intrinsic spread of a configuration in 𝑅^{𝑑}
inferred← citeshttps://doi.org/10.1109/cec.2008.4631195openalex-snapshot
A hybrid simulated annealing algorithm for the Bipartite Crossing Number Minimization Problem
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00098openalex-snapshot
Framework for ER-Completeness of Two-Dimensional Packing Problems
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00099openalex-snapshot
Smoothing the gap between NP and ER
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00045openalex-snapshot
Covering Polygons is Even Harder
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743512openalex-snapshot
Which crossing number is it, anyway? [computational geometry]
inferred← citeshttps://doi.org/10.1115/gt2004-54115openalex-snapshot
WIDGET-TEMP: A Novel Web-Based Approach for Thermoeconomic Analysis and Optimization of Conventional and Innovative Cycles
inferred← citeshttps://doi.org/10.1137/1.9781611975055.12openalex-snapshot
A Geometric Heuristic for Rectilinear Crossing Minimization
inferred← citeshttps://doi.org/10.1137/1.9781611977066.8openalex-snapshot
Topological Art in Simple Galleries
inferred← citeshttps://doi.org/10.1137/20m1385287openalex-snapshot
Smoothing the Gap Between NP and ER
inferred← citeshttps://doi.org/10.1142/s0218195913600029openalex-snapshot
SIMULTANEOUS EMBEDDING OF EMBEDDED PLANAR GRAPHS
inferred← citeshttps://doi.org/10.1145/1250790.1250848openalex-snapshot
Computing crossing number in linear time
inferred← citeshttps://doi.org/10.1145/1998196.1998248openalex-snapshot
Integer representations of convex polygon intersection graphs
inferred← citeshttps://doi.org/10.1145/2452376.2452439openalex-snapshot
Data exchange with arithmetic operations
inferred← citeshttps://doi.org/10.1145/2852040.2852053openalex-snapshot
Computational Geometry Column 62
inferred← citeshttps://doi.org/10.1145/3188745.3188868openalex-snapshot
The art gallery problem is ∃ ℝ-complete
inferred← citeshttps://doi.org/10.1145/3325861openalex-snapshot
Geometric Heuristics for Rectilinear Crossing Minimization
inferred← citeshttps://doi.org/10.1145/3486220openalex-snapshot
The Art Gallery Problem is ∃ℝ-complete
inferred← citeshttps://doi.org/10.1145/513400.513403openalex-snapshot
On the crossing number of complete graphs
inferred← citeshttps://doi.org/10.14279/depositonce-5580openalex-snapshot
Intersection graphs and geometric objects in the plane
inferred← citeshttps://doi.org/10.2307/1990931openalex-snapshot
The Intrinsic Spread of a Configuration in R d
inferred← citeshttps://doi.org/10.37236/1567openalex-snapshot
The Rectilinear Crossing Number of $K_{10}$ is $62$
inferred← citeshttps://doi.org/10.37236/2713openalex-snapshot
The Graph Crossing Number and its Variants: A Survey
inferred← citeshttps://doi.org/10.4230/lipics.esa.2019.76openalex-snapshot
Geometric Crossing-Minimization - A Scalable Randomized Approach
inferred← citeshttps://doi.org/10.46298/dmtcs.9225openalex-snapshot
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
inferred← citeshttps://doi.org/10.46298/theoretics.24.11openalex-snapshot
Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1101.3386openalex-snapshot
The crossing number of folded hypercubes
inferred← citeshttps://doi.org/10.48550/arxiv.1103.4227openalex-snapshot
The crossing number of locally twisted cubes
inferred← citeshttps://doi.org/10.48550/arxiv.1606.03753openalex-snapshot
Approximating the rectilinear crossing number
inferred← citeshttps://doi.org/10.48550/arxiv.1704.06969openalex-snapshot
The Art Gallery Problem is $\exists \mathbb{R}$-complete
inferred← citeshttps://doi.org/10.48550/arxiv.1808.07558openalex-snapshot
Crossing Numbers and Stress of Random Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1908.02213openalex-snapshot
A Universality Theorem for Nested Polytopes
inferred← citeshttps://doi.org/10.48550/arxiv.1908.09400openalex-snapshot
Optimal Curve Straightening is $\exists\mathbb{R}$-Complete
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0009023openalex-snapshot
The Rectilinear Crossing Number of K_10 is 62
inferred← citeshttps://doi.org/10.48550/arxiv.math/9910185openalex-snapshot
Geometric Thickness of Complete Graphs
inferred← citeshttps://doi.org/10.70675/c0b93ddcz747cz4e2fzb2a1zdccd7008991dopenalex-snapshot
Drawing graphs on surfaces of null and higher genus
inferred← citeshttps://doi.org/10.7155/jgaa.00023openalex-snapshot
Geometric Thickness of Complete Graphs
inferred← citeshttps://doi.org/10.7155/jgaa.00032openalex-snapshot
Planarizing Graphs - A Survey and Annotated Bibliography
inferred← citeshttps://doi.org/10.7155/jgaa.00557openalex-snapshot
On the Complexity of Some Geometric Problems With Fixed Parameters
inferred← citeshttps://doi.org/10.7155/jgaa.00586openalex-snapshot
Crossing Numbers of Beyond-Planar Graphs Revisited
inferred← citeshttps://doi.org/10.7155/jgaa.00602openalex-snapshot
The Complexity of Drawing a Graph in a Polygonal Region
inferred← citeshttps://doi.org/10.7155/jgaa.00630openalex-snapshot
The Complexity of Drawing Graphs on Few Lines and Few Planes
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.