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

DOI10.1007/978-3-540-74839-7_23MaRDI QIDQ3508571zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Graph Drawing
• Polygon Graph Recognition
• On the structure of certain intersection graphs
• Geometric Intersection Graphs: Do Short Cycles Help?
• String graphs. II: Recognizing string graphs is NP-hard

Cites work

• 3D-interval-filament graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Circle graph obstructions
• Covering and coloring polygon-circle graphs
• Efficient graph representations
• Geometric Intersection Graphs: Do Short Cycles Help?
• Graph Drawing
• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• scientific article; zbMATH DE number 125465 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Intersection graphs of curves in the plane
• Intersection graphs of Helly families of subtrees
• Intersection graphs of segments
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Recognition of Circle Graphs
• Recognizing string graphs in NP
• String graphs. II: Recognizing string graphs is NP-hard
• The complexity of satisfiability problems
• Topics in Intersection Graph Theory

Cited in

(19)

• Polygon-circle and word-representable graphs
• Algorithms for induced biclique optimization problems
• Succinct navigational oracles for families of intersection graphs on a circle
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• 3D-interval-filament graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders Is Polynomial
• Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Alternation graphs
• Algorithms on Subtree Filament Graphs
• Graph Drawing
• The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial
• Maximum max-k-clique subgraphs in cactus subtree graphs
• On 3-degree 4-chordal graphs
• Recognising the overlap graphs of subtrees of restricted trees is hard
• On-line approach to off-line coloring problems on graphs with geometric representations
• On the structure of certain intersection graphs
• Semi-transitive orientations and word-representable graphs

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

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