English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this paper, we study grid-obstacle representations of graphs where weassign grid-points to vertices and define obstacles such that an edge exists ifand only if an $xy$-monotone grid path connects the two endpoints withouthitting an obstacle or another vertex. It was previously argued that all planargraphs have a grid-obstacle representation in 2D, and all graphs have agrid-obstacle representation in 3D. In this paper, we show that suchconstructions are possible with significantly smaller grid-size than previouslyachieved. Then we study the variant where vertices are not blocking, and showthat then grid-obstacle representations exist for bipartite graphs. The latterhas applications in so-called staircase guarding of orthogonal polygons; usingour grid-obstacle representations, we show that staircase guarding is\textsc{NP}-hard in 2D.

Grid-Obstacle Representations with Connections to Staircase Guarding