Grid-obstacle representations with connections to staircase guarding

DOI10.1007/978-3-319-73915-1_7MaRDI QIDQ4625102zbMATH OpenOpenAlexFDO

Authors Saeed Mehrabi, Therese Biedl

Publication date 20 February 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.01903

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In this paper, we study grid-obstacle representations of graphs where we assign grid-points to vertices and define obstacles such that an edge exists if and only if an $xy$-monotone grid path connects the two endpoints without hitting an obstacle or another vertex. It was previously argued that all planar graphs have a grid-obstacle representation in 2D, and all graphs have a grid-obstacle representation in 3D. In this paper, we show that such constructions are possible with significantly smaller grid-size than previously achieved. Then we study the variant where vertices are not blocking, and show that then grid-obstacle representations exist for bipartite graphs. The latter has applications in so-called staircase guarding of orthogonal polygons; using our grid-obstacle representations, we show that staircase guarding is extsc{NP}-hard in 2D.

Recommendations

• Grid obstacle representation of graphs
• Graphs with no grid obstacle representation
• Geodesic obstacle representation of graphs
• Geodesic obstacle representation of graphs

Cites work

• A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
• A note on optimal area algorithms for upward drawings of binary trees
• A unified approach to visibility representations of planar graphs
• Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems
• Fully homomorphic encryption using ideal lattices
• scientific article; zbMATH DE number 1722670 (Why is no real title available?)
• scientific article; zbMATH DE number 1304185 (Why is no real title available?)
• More efficient commitments from structured lattice assumptions
• Multi-authority secret-ballot elections with linear work
• Obstacle numbers of graphs
• On lattices, learning with errors, random linear codes, and cryptography
• Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs
• Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function
• Unit disk graphs

Cited in

(5)

• Geodesic obstacle representation of graphs
• On orthogonally guarding orthogonal polygons with bounded treewidth
• Grid obstacle representation of graphs
• Graphs with no grid obstacle representation
• Geodesic obstacle representation of graphs

This page was built for publication: Grid-obstacle representations with connections to staircase guarding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625102)