Bounding and computing obstacle numbers of graphs
From MaRDI portal
Publication:6542540
DOI10.1137/23M1585088zbMATH Open1539.05104MaRDI QIDQ6542540
Alexander Wolff, Pavel Valtr, Robert Ganian, Author name not available (Why is that?), Siddharth Gupta, Steven Chaplick, Martin Balko
Publication date: 22 May 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Erd?s problems and related topics of discrete geometry (52C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Title not available (Why is that?)
- Fundamentals of parameterized complexity
- Lower bounds on the obstacle number of graphs
- Recognition and complexity of point visibility graphs
- Coding and counting arrangements of pseudolines
- Obstacle numbers of graphs
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Axioms and hulls
- Drawing graphs using a small number of obstacles
- On a problem of formal logic.
- Some results on point visibility graphs
- On obstacle numbers
- Obstructing Visibilities with One Obstacle
- Reconstructing Point Set Order Types from Radial Orderings
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Obstacle Numbers of Planar Graphs
- Outside-obstacle representations with all vertices on the outer face
This page was built for publication: Bounding and computing obstacle numbers of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6542540)
