Some results on visibility graphs

DOI10.1016/0166-218X(92)90018-6zbMath0781.05013MaRDI QIDQ1201816

Thomas Andreae

Publication date: 17 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

embeddingplanar graphsNP-completevisibility graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Applications of graph theory to circuits and networks (94C15) Eulerian and Hamiltonian graphs (05C45)

Related Items (9)

Bar visibility numbers for hypercubes and outerplanar digraphs ⋮ Area requirement of visibility representations of trees ⋮ Rectangle-visibility representations of bipartite graphs ⋮ Determining bar-representability for ordered weighted graphs ⋮ Special graph representation and visualization of semantic networks ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Disproving a conjecture on planar visibility graphs ⋮ The partial visibility representation extension problem ⋮ A necessary condition for a graph to be the visibility graph of a simple polygon

Cites Work

• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Matching theory
• A note on visibility graphs
• Representing orders on the plane by translating convex figures
• Algorithms for plane representations of acyclic digraphs
• Representations of Graphs on a Cylinder
• An application of graph coloring to printed circuit testing
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Minimum partition of a matroid into independent subsets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some results on visibility graphs