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

DOI10.1016/J.IPL.2018.05.002zbMATH Open1478.68212OpenAlexW2804464011WikidataQ62046541 ScholiaQ62046541MaRDI QIDQ1641160FDOQ1641160

Authors: Patrizio Angelini, Giordano Da Lozzo 

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

Recommendations

• NP-completeness of slope-constrained drawing of complete graphs
• Thickness and colorability of geometric graphs
• The interval constrained 3-coloring problem
• A note on coloring line arrangements
• The interval constrained 3-coloring problem

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• On coloring unit disk graphs
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• On a Coloring Problem.
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Coloring intersection graphs of arc-connected sets in the plane
• Testing bipartiteness of geometric intersection graphs
• Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs

Cited In (2)

• Proper colorability of segment intersection graphs
• NP-completeness of slope-constrained drawing of complete graphs

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

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