The complexity of colouring circle graphs (extended abstract)

DOI10.1007/3-540-55210-3_199MaRDI QIDQ5096797zbMATH OpenOpenAlexWikidataFDO

Authors Walter Unger

Publication date 18 August 2022

Published in STACS 92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55210-3_199

zbMATH Keywords

circle graphscomputational complexitygraph colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) 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

• scientific article; zbMATH DE number 4051024
• scientific article; zbMATH DE number 52166
• The complexity of some graph colouring problems
• Coloring circle graphs
• Improved bounds for colouring circle graphs

Cites work

• A characterization of circle graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An O(n^2 ) Algorithm for Coloring Proper Circular Arc Graphs
• An Efficient Test for Circular-Arc Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Finding maximum cliques in circle graphs
• scientific article; zbMATH DE number 3970805 (Why is no real title available?)
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• scientific article; zbMATH DE number 52166 (Why is no real title available?)
• scientific article; zbMATH DE number 3997838 (Why is no real title available?)
• Orientations of circle graphs
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(25)

• Container ship stowage problem complexity and connection to the coloring of circle graphs
• On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
• Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
• Parameterized analysis and crossing minimization problems
• Parameterized algorithms for book embedding problems
• 2-stack sorting is polynomial
• On polygon numbers of circle graphs and distance hereditary graphs
• Parameterized domination in circle graphs
• On the complexity of container stowage planning problems
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Coloring circle graphs
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• scientific article; zbMATH DE number 52166 (Why is no real title available?)
• Improved bounds for colouring circle graphs
• Upward book embeddings of st-graphs
• Parameterized algorithms for book embedding problems
• On the exact complexity of Hamiltonian Cycle and \(q\)-Colouring in disk graphs
• Sorting with networks of data structures
• Upward book embeddability of \(st\)-graphs: complexity and algorithms
• On 3-coloring circle graphs
• On 3-coloring circle graphs
• Eliminating crossings in ordered graphs
• The parameterized complexity of extending stack layouts
• Forbidden patterns in mixed linear layouts
• The parameterized complexity of extending stack layouts

This page was built for publication: The complexity of colouring circle graphs (extended abstract)

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