Can visibility graphs be represented compactly?

DOI10.1007/BF02574385MaRDI QIDQ1338961zbMATH OpenDBLPWikidataFDO

Authors Noga Alon, Subhash Suri, Pankaj K. Agarwal, Boris Aronov

Publication date 27 November 1994

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

Full work available at URL https://eudml.org/doc/131336

zbMATH Keywords

clique covervisibility graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Some results on visibility graphs
• scientific article; zbMATH DE number 1759472
• Minimal visibility graphs
• Computing the maximum clique in the visibility graph of a simple polygon
• A tight lower bound on the size of visibility graphs

Cites work

• scientific article; zbMATH DE number 742950 (Why is no real title available?)
• scientific article; zbMATH DE number 3238444 (Why is no real title available?)
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Computing the longest diagonal of a simple polygon
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Visibility and intersection problems in plane geometry

Cited in

(23)

• Extractors in Paley graphs: a random model
• New lower bounds for Hopcroft's problem
• On counting point-hyperplane incidences
• On the chromatic number of random Cayley graphs
• Vertical visibility among parallel polygons in three dimensions
• Area requirement of visibility representations of trees
• Random Latin square graphs
• Large-scale clique cover of real-world networks
• Consensus algorithms for the generation of all maximal bicliques
• Topologically sweeping visibility complexes via pseudotriangulations
• Alternating paths along axis-parallel segments
• Representation complexities of semialgebraic graphs
• Bi-objective optimization of biclustering with binary data
• scientific article; zbMATH DE number 1759472 (Why is no real title available?)
• Planar segment visibility graphs
• scientific article; zbMATH DE number 4049090 (Why is no real title available?)
• Perfect Graphs and Orthogonally Convex Covers
• On the kernel size of clique cover reductions for random intersection graphs
• Arboricity and bipartite subgraph listing algorithms
• On computing the Galois lattice of bipartite distance hereditary graphs
• Segment endpoint visibility graphs are Hamiltonian
• Clique Cover and Graph Separation
• An algorithm for the difference between set covers

This page was built for publication: Can visibility graphs be represented compactly?

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