Bounding and computing obstacle numbers of graphs

DOI10.4230/LIPICS.ESA.2022.11MaRDI QIDQ6969678zbMATH OpenFDO

Authors Martin Balko, Steven Chaplick, Robert Ganian, Siddharth Gupta, Pavel Valtr, Alexander Wolff

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.11

zbMATH Keywords

FPTNP-hardnessobstacle numberobstacle representationvisibility

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Axioms and hulls
• Bounding and computing obstacle numbers of graphs
• Coding and counting arrangements of pseudolines
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Drawing graphs using a small number of obstacles
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 431988 (Why is no real title available?)
• Lower bounds on the obstacle number of graphs
• Obstacle numbers of graphs
• Obstacle numbers of planar graphs
• Obstructing visibilities with one obstacle
• On a problem of formal logic.
• On obstacle numbers
• Recognition and complexity of point visibility graphs
• Reconstructing Point Set Order Types from Radial Orderings
• Some results on point visibility graphs
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)

Cited in

(2)

• Weakly leveled planarity with bounded span
• Bounding and computing obstacle numbers of graphs

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 Q6969678)