complexitydecisionintersection graphsNP-completerecognitionrecognition problempolynomial inequalitiessegmentsmembership problemSEG- 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)
Recommendations
Cited in
(89)- Some provably hard crossing number problems
- Finding geometric representations of apex graphs is NP-hard
- The complexity of drawing a graph in a polygonal region
- scientific article; zbMATH DE number 7559240 (Why is no real title available?)
- Topological queries in spatial databases
- Not all planar graphs are in PURE-4-DIR
- Faster 3-coloring of small-diameter graphs
- String graphs of \(k\)-bend paths on a grid
- The complexity of recognizing geometric hypergraphs
- Order-preserving 1-string representations of planar graphs
- Proper colorability of segment intersection graphs
- On classifying continuous constraint satisfaction problems
- On the speed of algebraically defined graph classes
- On the complexity of recognizing nerves of convex sets
- Segment representations with small resolution
- scientific article; zbMATH DE number 2084282 (Why is no real title available?)
- Intersection graphs of L-shapes and segments in the plane
- Drawing plane triangulations with few segments
- The clique problem in ray intersection graphs
- Segment representation of a subclass of co-planar graphs
- Computing list homomorphisms in geometric intersection graphs
- Finding hidden independent sets in interval graphs
- On the complexity of planar covering of small graphs
- Optimality program in segment and string graphs
- Using graph concepts to assess the feasibility of a sequenced air traffic flow with low conflict rate
- The complexity of tensor rank
- Representations by contact and intersection of segments
- Integer representations of convex polygon intersection graphs
- Intersection graphs of halflines and halfplanes
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- The Complexity of Drawing Graphs on Few Lines and Few Planes
- Forced pairs in \(A\)-Stick graphs
- Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
- Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
- The number of bits needed to represent a unit disk graph
- Intersection graphs of pseudosegments: chordal graphs
- Stick graphs with length constraints
- Vertex intersection graphs of paths on a grid: characterization within block graphs
- Untangling a planar graph
- Recognizing stick graphs with and without length constraints
- A separator theorem for string graphs and its applications
- Sign rank versus Vapnik-Chervonenkis dimension
- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
- Classes and recognition of curve contact graphs
- Embedding ray intersection graphs and global curve simplification
- Crossing patterns of segments
- The maximal clique and colourability of curve contact graphs
- Thresholds for classes of intersection graphs
- scientific article; zbMATH DE number 7559254 (Why is no real title available?)
- Representing graphs and hypergraphs by touching polygons in 3D
- A special planar satisfiability problem and a consequence of its NP- completeness
- Constraint satisfaction problems over numeric domains
- Homothetic polygons and beyond: maximal cliques in intersection graphs
- On unit grid intersection graphs and several other intersection graph classes
- Orientation preserving maps of the square grid II
- Every planar graph is the intersection graph of segments in the plane (extended abstract)
- The complexity of the partial order dimension problem: closing the gap
- Proper colorability of segment intersection graphs
- Integer representations of convex polygon intersection graphs
- The complexity of drawing a graph in a polygonal region
- scientific article; zbMATH DE number 4158672 (Why is no real title available?)
- Optimal grid representations
- Intersection graphs and geometric objects in the plane
- B0-VPG Representation of AT-free Outerplanar Graphs
- Intersections and circuits in sets of line segments
- On the chromatic number of disjointness graphs of curves
- On orthogonal ray trees
- Complexity of some geometric and topological problems
- Beyond the Existential Theory of the Reals
- Intersection graphs of rays and grounded segments
- Intersection graphs of rays and grounded segments
- Finding geometric representations of apex graphs is \textsf{NP}-hard
- \(B_0\)-VPG representation of AT-free outerplanar graphs
- A Separator Theorem for String Graphs and Its Applications
- On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
- Recognition and complexity of point visibility graphs
- Graphs of intersections of closed polygonal chains
- On the complexity of the planar slope number problem
- On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
- Contact graphs of line segments are NP-complete
- Independent set of intersection graphs of convex objects in 2D
- On sets of line segments featuring a cactus structure
- Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- Fixed points, Nash equilibria, and the existential theory of the reals
- Simple realizability of complete abstract topological graphs in P
- Refining the hierarchies of classes of geometric intersection graphs
- Refining the hierarchies of classes of geometric intersection graphs
- Testing bipartiteness of geometric intersection graphs
This page was built for publication: Intersection graphs of segments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1338319)
