{"entities":{"Q5937922":{"pageid":8114724,"ns":120,"title":"Item:Q5937922","lastrevid":47642302,"modified":"2026-01-02T07:16:34Z","type":"item","id":"Q5937922","labels":{"en":{"language":"en","value":"Contact graphs of line segments are NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1621231"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937922$543F5556-0C19-4B13-80AD-90795CE5D96B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46f26dec0db5f3be3d2b68a7e90c7d27d0e83c04","datavalue":{"value":{"text":"Contact graphs of line segments are NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937922$9F570F07-0275-49D6-92BB-9CB25967FC17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b890ddf3207d0abf28e3b54b68061326a0fabb5","datavalue":{"value":"0982.05083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937922$5FC09FBF-C349-45E9-8669-231A14F78336","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51def25967c005abf4e8dccc0e5454c7140eb5f9","datavalue":{"value":"10.1016/S0012-365X(00)00263-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937922$B44A95EE-D543-4BF0-A44C-636E9BA02BE8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f97addcae0de185068af846d9968c1df864cbf3","datavalue":{"value":{"entity-type":"item","numeric-id":175586,"id":"Q175586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937922$0A71FD76-5BC7-4737-8D85-7CBD7929F95E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937922$22A947B6-B52D-4B1D-88CA-36E9FFD62848","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d523614f519ec0feabed1eeb5eb67171dc8b190","datavalue":{"value":{"time":"+2002-03-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937922$16D59605-D7A9-4D12-BDEF-4D74AE10B9E1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"81bd7b6a2a7a2c666ae828bb2dfb9665a2dfcf86","datavalue":{"value":"Contact graphs of line segments are intersection graphs of a family of line segments in the plane such that every two distinct line segments in the family have no common interior point. By reducing PLANAR 3-SAT, the author proves that the recognition problem of contact graphs of line segments is NP-complete, even for planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937922$6FA24079-417F-4B7B-9F50-0D52604B4F64","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937922$200893C2-7F0C-4FBC-99E6-E2BAE225BB9A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937922$58866872-9475-44DB-966D-86BD260C633F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937922$096E0E5E-B95F-4031-85E7-18CEB0990500","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f0203044bf495881181aecfbd281a3d740f600f","datavalue":{"value":"1621231","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937922$CAACE0A6-13EC-427A-BBE1-23A17DC7C406","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cf57a2af64e82dba585f0ddfd3928081b5afff2","datavalue":{"value":"contact graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937922$9937A4D5-1EFA-4151-9DFF-8A915A584EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937922$45C1AEF6-4130-448E-BC67-3DB3FFE25E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937922$C924F97E-5A1C-4AC6-8C9F-7AC92539C2FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51c0410216f6db1f0aaf7ec78f4b1eb7c20b723a","datavalue":{"value":"recognition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937922$96195F05-ADA3-4D0F-B6CA-50BACFAFC58D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937922$FA5965C2-3F31-4993-B8F2-97C96C885397","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0e3f0a0b6871939a2a18f34b3374983231c389c1","datavalue":{"value":"Q127343765","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937922$D4DBA8FD-139C-4A0F-BD92-89A022C896CB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b96c195b35ed332c03cbb12002cd7aa97f19144","datavalue":{"value":{"entity-type":"item","numeric-id":1272471,"id":"Q1272471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7258c1a4b6ad97cb8802fef6d276f183bf5a275f","datavalue":{"value":{"amount":"+0.8627511262893677","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937922$C6BD24FB-51BF-4B92-938E-9D14A01821D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec06c778164d9610d69bccc68fcf71060b870732","datavalue":{"value":{"entity-type":"item","numeric-id":1338319,"id":"Q1338319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5264f1504cc9f16febb08cd5d3ffbbc4ac147216","datavalue":{"value":{"amount":"+0.8173956871032715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937922$AB71E4A6-8E40-49B1-A2DD-5A842271C5D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c8e5dd5ce8b56199bef83f40f0ad15141b9dada","datavalue":{"value":{"entity-type":"item","numeric-id":1382253,"id":"Q1382253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9921a5b7dc5067eb78aca4e5202f9b779ee76999","datavalue":{"value":{"amount":"+0.812118649482727","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937922$2C638DE3-5444-4904-A7AE-8524FEEBBE53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ab6eba57e1bde35b5873445bf973db86eb9066b","datavalue":{"value":{"entity-type":"item","numeric-id":2945185,"id":"Q2945185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"731b2dd3b1a30eac1699c54d77e74f4fed6f0cb8","datavalue":{"value":{"amount":"+0.8121185898780823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937922$A0897C13-DB64-47A2-A4B4-7726CAA23949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b20e1807c536a86a6c744fdcf27ef729fe6eb681","datavalue":{"value":{"entity-type":"item","numeric-id":3474685,"id":"Q3474685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7091e57b60b6bfd05db48cd27b66f854277ab762","datavalue":{"value":{"amount":"+0.8120429515838623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5937922$11312F0A-693D-4207-909A-20A3E89E8B89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937922","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937922"}}}}}