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

DOI10.1016/J.TCS.2023.113773MaRDI QIDQ2693628zbMATH OpenOpenAlexFDO

Authors 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

BipHook graphintersection graphmax point-tolerance graphNP-hardnessStick graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Recognizing stick graphs with and without length constraints
• Forced pairs in \(A\)-Stick graphs
• Contact graphs of line segments are NP-complete

Cites work

• p-box: a new graph model
• A special planar satisfiability problem and a consequence of its NP- completeness
• Algorithmic Aspects of Vertex Elimination on Graphs
• Complexity of some geometric and topological problems
• Forced pairs in \(A\)-Stick graphs
• Graph Classes: A Survey
• Grid intersection graphs and order dimension
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Intersection graphs of rays and grounded segments
• Intersection graphs of segments
• Max point-tolerance graphs
• On grid intersection graphs
• On orthogonal ray graphs
• Recognizing stick graphs with and without length constraints
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of satisfiability problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics in Intersection Graph Theory
• Topology of Thin Film RC Circuits

Cited in

(5)

• Forced pairs in \(A\)-Stick graphs
• Stick graphs with length constraints
• Recognizing stick graphs with and without length constraints
• Recognizing geometric intersection graphs stabbed by a line
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words

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

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