Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete

DOI10.1007/978-3-540-74839-7_23zbMath1141.68547OpenAlexW1576190294MaRDI QIDQ3508571

Martin Pergel

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS ⋮ Cops and robbers on intersection graphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ On 3-degree 4-chordal graphs ⋮ Algorithms for induced biclique optimization problems ⋮ Semi-transitive orientations and word-representable graphs ⋮ Polygon-circle and word-representable graphs ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ Alternation Graphs ⋮ Algorithms on Subtree Filament Graphs ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• String graphs. II: Recognizing string graphs is NP-hard
• Intersection graphs of curves in the plane
• Circle graph obstructions
• Intersection graphs of segments
• Covering and coloring polygon-circle graphs
• Efficient graph representations
• Intersection graphs of Helly families of subtrees
• 3D-interval-filament graphs
• Geometric Intersection Graphs: Do Short Cycles Help?
• Algorithmic Aspects of Vertex Elimination on Graphs
• Topics in Intersection Graph Theory
• Recognition of Circle Graphs
• Graph Drawing
• The complexity of satisfiability problems
• Recognizing string graphs in NP

This page was built for publication: Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete