Stick graphs with length constraints

DOI10.1007/978-3-030-35802-0_1OpenAlexW2990562807MaRDI QIDQ2206824

Alexander Wolff, Philipp Kindermann, Alexander Zaft, Florian Thiele, Andre Löffler, Steven Chaplick, 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)

Related Items

Forced pairs in \(A\)-Stick graphs ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Recognition and drawing of stick 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
• Bipartite permutation graphs
• On grid intersection graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• 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
• Intersection Graphs of L-Shapes and Segments in the Plane
• 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
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• 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