Recognizing Stick Graphs with and without Length Constraints

DOI10.7155/jgaa.00524zbMath1451.05223OpenAlexW3011662039MaRDI QIDQ5141646

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

Publication date: 18 December 2020

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00524

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs

Cites Work

• Unnamed Item
• Max point-tolerance graphs
• Ferrers dimension of grid intersection graphs
• Interval graph representation with given interval and intersection lengths
• Grid intersection graphs and order dimension
• On grid intersection graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Intersection graphs of segments
• Two-segmented channel routing is strong NP-complete
• On the classes of interval graphs of limited nesting and count of lengths
• Stick graphs with length constraints
• Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Complexity of Some Geometric and Topological Problems
• Realizing Interval Graphs with Size and Distance Constraints
• Intersection Graphs of Rays and Grounded Segments
• Every planar graph is the intersection graph of segments in the plane
• Refining the hierarchies of classes of geometric intersection graphs
• Recognition and drawing of stick graphs

This page was built for publication: Recognizing Stick Graphs with and without Length Constraints