Recognizing stick graphs with and without length constraints

Publication date 18 December 2020

Recommendations

Cites work

scientific article; zbMATH DE number 3639144 (Why is no real title available?)
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
Complexity of some geometric and topological problems
Contact representations of planar graphs: extending a partial representation is hard
Every planar graph is the intersection graph of segments in the plane (extended abstract)
Ferrers dimension of grid intersection graphs
Grid intersection graphs and order dimension
Intersection graphs of rays and grounded segments
Intersection graphs of segments
Interval graph representation with given interval and intersection lengths
Max point-tolerance graphs
On grid intersection graphs
On the classes of interval graphs of limited nesting and count of lengths
Realizing Interval Graphs with Size and Distance Constraints
Refining the hierarchies of classes of geometric intersection graphs
Stick graphs with length constraints
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Two-segmented channel routing is strong NP-complete

Cited in

(5)

Forced pairs in \(A\)-Stick graphs
Stick graphs with length constraints
Planar straight-line realizations of 2-trees with prescribed edge lengths
Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
On the complexity of recognizing Stick, BipHook and max point-tolerance graphs

This page was built for publication: Recognizing stick graphs with and without length constraints