Stick graphs with length constraints

DOI10.1007/978-3-030-35802-0_1MaRDI QIDQ2206824zbMATH OpenOpenAlexFDO

Authors Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele, Alexander Wolff, Alexander Zaft, Johannes Zink

Publication date 26 October 2020

Full work available at URL https://arxiv.org/abs/1907.05257

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Recognizing stick graphs with and without length constraints
• Forced pairs in \(A\)-Stick graphs
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Bipartite permutation graphs
• 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
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Intersection graphs of L-shapes and segments in the plane
• 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
• Two-segmented channel routing is strong NP-complete

Cited in

(3)

• Forced pairs in \(A\)-Stick graphs
• Recognizing stick graphs with and without length constraints
• Stick graphs with length constraints

This page was built for publication: Stick graphs with length constraints

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