Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graphs

DOI10.1142/S1793830911001243MaRDI QIDQ2890989zbMATH OpenOpenAlexFDO

Authors Fanica Gavril

Publication date 12 June 2012

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830911001243

zbMATH Keywords

polygon-circle graphcircle graphmaximum induced forestminimum feedback vertex setcircle trapezoid graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Minimum weight feedback vertex sets in circle graphs
• Polygon Graph Recognition
• Graph Drawing
• Circular convex bipartite graphs: feedback vertex set
• Circular convex bipartite graphs: feedback vertex sets

Cites work

• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• 3D-interval-filament graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Feedback vertex set on AT-free graphs
• Feedback vertex set on cocomparability graphs
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Minimum weight feedback vertex sets in circle graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• The Complexity of Coloring Circular Arcs and Chords
• The maximum k-colorable subgraph problem for chordal graphs
• Thresholds for classes of intersection graphs
• Trapezoid graphs and generalizations, geometry and algorithms

Cited in

(2)

• Minimum weight feedback vertex sets in circle graphs
• Large Induced Subgraphs via Triangulations and CMSO

This page was built for publication: Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs

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