Can visibility graphs be represented compactly?

DOI10.1007/BF02574385zbMath0819.68134WikidataQ56001794 ScholiaQ56001794MaRDI QIDQ1338961

Subhash Suri, Noga Alon, 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

visibility graphclique cover

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)

Related Items (19)

On computing the Galois lattice of bipartite distance hereditary graphs ⋮ On counting point-hyperplane incidences ⋮ Arboricity and bipartite subgraph listing algorithms ⋮ Area requirement of visibility representations of trees ⋮ Random Latin square graphs ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Bi-objective optimization of biclustering with binary data ⋮ Alternating paths along axis-parallel segments ⋮ Clique Cover and Graph Separation ⋮ Segment endpoint visibility graphs are Hamiltonian ⋮ On the Chromatic Number of Random Cayley Graphs ⋮ On the kernel size of clique cover reductions for random intersection graphs ⋮ An algorithm for the difference between set covers ⋮ Consensus algorithms for the generation of all maximal bicliques ⋮ Extractors in Paley graphs: a random model ⋮ Large-scale clique cover of real-world networks ⋮ New lower bounds for Hopcroft's problem ⋮ Topologically sweeping visibility complexes via pseudotriangulations ⋮ Representation Complexities of SemiAlgebraic Graphs

Cites Work

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

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