On the complexity of recognizing Stick, BipHook and max point-tolerance graphs

DOI10.1016/j.tcs.2023.113773OpenAlexW4307685942MaRDI QIDQ2693628

Irena Rusu

Publication date: 24 March 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

intersection graphNP-hardnessBipHook graphmax point-tolerance graphStick graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Recognizing geometric intersection graphs stabbed by a line

Cites Work

• Unnamed Item
• Max point-tolerance graphs
• On orthogonal ray graphs
• 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
• A special planar satisfiability problem and a consequence of its NP- completeness
• Intersection graphs of segments
• Forced pairs in \(A\)-Stick graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Complexity of Some Geometric and Topological Problems
• Algorithmic Aspects of Vertex Elimination on Graphs
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Intersection Graphs of Rays and Grounded Segments
• Recognizing Stick Graphs with and without Length Constraints
• (c-)AND: A new graph model
• The complexity of satisfiability problems
• Topology of Thin Film RC Circuits
• Recognition and drawing of stick graphs

This page was built for publication: On the complexity of recognizing Stick, BipHook and max point-tolerance graphs