3-coloring arrangements of line segments with 4 slopes is hard

DOI10.1016/j.ipl.2018.05.002zbMath1478.68212OpenAlexW2804464011WikidataQ62046541 ScholiaQ62046541MaRDI QIDQ1641160

Giordano Da Lozzo, Patrizio Angelini

Publication date: 15 June 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.05.002

zbMATH Keywords

computational complexityintersection graphs3-colorabilityconstrained geometric thicknessplanar stratification of geometric graph drawings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Coloring intersection graphs of arc-connected sets in the plane
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• On coloring unit disk graphs
• On a Coloring Problem.
• Topics in Intersection Graph Theory
• Unnamed Item
• Unnamed Item

This page was built for publication: 3-coloring arrangements of line segments with 4 slopes is hard