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

DOI10.1016/J.IPL.2018.05.002MaRDI QIDQ1641160zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

3-colorabilitycomputational complexityconstrained geometric thicknessintersection graphsplanar stratification of geometric graph drawings

Mathematics Subject Classification ID

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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

Cites work

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

Cited in

(3)

• 3-colorable planar graphs have an intersection segment representation using 3 slopes
• NP-completeness of slope-constrained drawing of complete graphs
• Proper colorability of segment intersection 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)