Combinatorial properties and recognition of unit square visibility graphs

DOI10.1007/s00454-022-00414-8OpenAlexW2963622148MaRDI QIDQ6045782

Markus L. Schmid, Katrin Casel, Alexander Grigoriev, Henning Fernau, S. H. Whitesides

Publication date: 12 May 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-022-00414-8

zbMATH Keywords

visibility graphsgraph recognition\textsf{NP}-completenessvisibility layoutgeometric graph classes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• Drawing graphs with right angle crossings
• The partial visibility representation extension problem
• Ortho-polygon visibility representations of embedded graphs
• A characterization of complete bipartite RAC graphs
• Unit rectangle visibility graphs
• Representing a planar graph by vertical lines joining different levels
• A unified approach to visibility representations of planar graphs
• The complexity of minimizing wire lengths in VLSI layouts
• Rectangle-visibility representations of bipartite graphs
• Visibility representations of boxes in 2.5 dimensions
• The Unit Bar Visibility Number of a Graph
• Rectangle and Square Representations of Planar Graphs
• On k-visibility graphs
• Obstructing Visibilities with One Obstacle
• Maximizing the Total Resolution of Graphs
• Complexity of Finding Non-Planar Rectilinear Drawings of Graphs
• Drawing Graphs in the Plane with High Resolution
• The Straight-Line RAC Drawing Problem is NP-Hard
• On Rectilinear Drawing of Graphs
• A Visibility Representation for Graphs in Three Dimensions
• A Note on Rectilinearity and Angular Resolution
• Two-Planar Graphs Are Quasiplanar
• Bar k-Visibility Graphs
• The complexity of satisfiability problems

This page was built for publication: Combinatorial properties and recognition of unit square visibility graphs