Can they cross? and how?

DOI10.1145/1998196.1998208zbMath1283.68371OpenAlexW1976802224MaRDI QIDQ5404410

Jan Kratochvíl

Publication date: 24 March 2014

Published in: Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1998196.1998208

zbMATH Keywords

complexityintersection graphNP-completeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

3-coloring \(C_4\) or \(C_3\)-free diameter two graphs ⋮ Faster 3-Coloring of Small-Diameter Graphs

This page was built for publication: Can they cross? and how?