Combinatorial properties and recognition of unit square visibility graphs

DOI10.4230/LIPICS.MFCS.2017.30zbMATH Open1441.68169arXiv1706.05906MaRDI QIDQ5111244FDOQ5111244

Authors: Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, Sue Whitesides 

Publication date: 26 May 2020

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

Recommendations

• Unit rectangle visibility graphs
• scientific article; zbMATH DE number 1962799
• Recognition and complexity of point visibility graphs
• Unit stack visibility graphs
• scientific article; zbMATH DE number 5976585

zbMATH Keywords

exact algorithmsNP-completenessvisibility graphsvisibility layout

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• The complexity of satisfiability problems
• A unified approach to visibility representations of planar graphs
• Drawing graphs with right angle crossings
• Rectangle and Square Representations of Planar Graphs
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• Title not available (Why is that?)
• Representing a planar graph by vertical lines joining different levels
• On \(k\)-visibility graphs
• Bar k-Visibility Graphs
• Maximizing the total resolution of graphs
• On visibility representations of non-planar graphs
• The complexity of minimizing wire lengths in VLSI layouts
• Complexity of finding non-planar rectilinear drawings of graphs
• A Note on Rectilinearity and Angular Resolution
• Rectangle-visibility representations of bipartite graphs
• Drawing Graphs in the Plane with High Resolution
• The straight-line RAC drawing problem is NP-hard
• Unit rectangle visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs
• A Visibility Representation for Graphs in Three Dimensions
• Obstructing visibilities with one obstacle
• On Rectilinear Drawing of Graphs
• The unit bar visibility number of a graph

Cited In (5)

• Simultaneous visibility representations of undirected pairs of graphs
• Graph isomorphism for unit square graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Unit rectangle visibility graphs

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

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