Bounding and computing obstacle numbers of graphs
From MaRDI portal
Publication:6542540
DOI10.1137/23M1585088zbMATH Open1539.05104MaRDI QIDQ6542540FDOQ6542540
Authors: Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Pavel Valtr, Alexander Wolff 
Publication date: 22 May 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Erd?s problems and related topics of discrete geometry (52C10)
Cites Work
- Fundamentals of parameterized complexity
- Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Axioms and hulls
- Title not available (Why is that?)
- Coding and counting arrangements of pseudolines
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- 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
- Lower bounds on the obstacle number of graphs
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- Some results on point visibility graphs
- Recognition and complexity of point visibility graphs
- On a problem of formal logic.
- Obstacle numbers of graphs
- Obstructing Visibilities with One Obstacle
- Drawing graphs using a small number of obstacles
- On obstacle numbers
- Obstacle Numbers of Planar Graphs
- Reconstructing Point Set Order Types from Radial Orderings
- 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)
