Contact graphs of line segments are NP-complete

DOI10.1016/S0012-365X(00)00263-6zbMath0982.05083WikidataQ127343765 ScholiaQ127343765MaRDI QIDQ5937922

Petr Hliněný

Publication date: 29 March 2002

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

intersection graphNP-completenesscontact graphrecognition problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Related Items (9)

Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Computing stable Demers cartograms ⋮ Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count ⋮ On contact graphs of paths on a grid ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs ⋮ Proportional Contact Representations of Planar Graphs ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ Unnamed Item

This page was built for publication: Contact graphs of line segments are NP-complete