Intersection graphs of segments
From MaRDI portal
Publication:1338319
DOI10.1006/jctb.1994.1071zbMath0808.68075OpenAlexW2006753964MaRDI QIDQ1338319
Jan Kratochvíl, Ji{ří} Matoušek
Publication date: 5 January 1995
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1994.1071
complexitydecisionrecognitionmembership problemNP-completerecognition problemintersection graphspolynomial inequalitiessegmentsSEG- graphssegment representation
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Complexity of computation (including implicit computational complexity) (03D15) Line geometries and their generalizations (51M30)
Related Items
A special planar satisfiability problem and a consequence of its NP- completeness ⋮ Intersection graphs of L-shapes and segments in the plane ⋮ Drawing plane triangulations with few segments ⋮ Finding hidden independent sets in interval graphs ⋮ The Complexity of Drawing a Graph in a Polygonal Region ⋮ On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs ⋮ Embedding ray intersection graphs and global curve simplification ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Homothetic polygons and beyond: maximal cliques in intersection graphs ⋮ The clique problem in ray intersection graphs ⋮ The maximal clique and colourability of curve contact graphs ⋮ Vertex intersection graphs of paths on a grid: characterization within block graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ The Complexity of Drawing Graphs on Few Lines and Few Planes ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ The Complexity of the Partial Order Dimension Problem: Closing the Gap ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Segment representation of a subclass of co-planar graphs ⋮ Proper colorability of segment intersection graphs ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ Simple realizability of complete abstract topological graphs in P ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ On orthogonal ray trees ⋮ Not all planar graphs are in PURE-4-DIR ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ On the Complexity of the Planar Slope Number Problem ⋮ Stick graphs with length constraints ⋮ Representing graphs and hypergraphs by touching polygons in 3D ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Unnamed Item ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ The complexity of drawing a graph in a polygonal region ⋮ Some provably hard crossing number problems ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ On the speed of algebraically defined graph classes ⋮ Recognition and complexity of point visibility graphs ⋮ Fixed points, Nash equilibria, and the existential theory of the reals ⋮ Optimal grid representations ⋮ Thresholds for classes of intersection graphs ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Crossing patterns of segments ⋮ The Number of Bits Needed to Represent a Unit Disk Graph ⋮ A Separator Theorem for String Graphs and its Applications ⋮ The complexity of tensor rank ⋮ A Separator Theorem for String Graphs and Its Applications ⋮ Using graph concepts to assess the feasibility of a sequenced air traffic flow with low conflict rate ⋮ Optimality program in segment and string graphs ⋮ Planar point sets determine many pairwise crossing segments ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Classes and recognition of curve contact graphs ⋮ On the Complexity of Planar Covering of Small Graphs ⋮ Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid ⋮ String graphs of k-bend paths on a grid ⋮ On the chromatic number of disjointness graphs of curves ⋮ Untangling a planar graph ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Segment representations with small resolution ⋮ Topological queries in spatial databases ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs
