{"entities":{"Q1112845":{"pageid":1123594,"ns":120,"title":"Item:Q1112845","lastrevid":42882460,"modified":"2025-07-15T16:49:26Z","type":"item","id":"Q1112845","labels":{"en":{"language":"en","value":"String graphs. II: Recognizing string graphs is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4079477"}},"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":"Q1112845$F1FE2182-8686-487D-8DB6-4F3F0D3866D3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6e8104e4203758681960e978eea4fa8fa2f24ea2","datavalue":{"value":{"text":"String graphs. II: Recognizing string graphs is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112845$549AA1C8-1EB4-428D-A8C7-10F1D8050E7A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6ff90bc7f71e33703470df30f89b19fb34465e6","datavalue":{"value":"0661.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112845$7D8D7500-45E4-4E3B-BB8B-7F922DDF0F0A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e3b7af8e5e1d213b57c008e02fdfbbf8ee2cdeb","datavalue":{"value":"10.1016/0095-8956(91)90091-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112845$5C4BCDAF-FD35-4D8C-8A86-92679E5C30E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$A1689781-AACE-4FC2-89D9-7DE61217E040","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$EC5058EB-90E1-4C1A-B0D7-644E0994F95C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1112845$CC027E4A-00D4-4598-A5EE-1F85E1F840E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9856f060a451b9fe8136e1d46a5c6f873f30b19","datavalue":{"value":"A graph is called a string graph if it is isomorphic to the intersection graph of a system of Jordan curves in the plane. It has been a long standing open problem whether string graphs can be recognized in polynomial time. Here we prove that recognizing string graphs and some related problems are NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112845$1479E2E8-EF65-4A2B-91F3-FCD8AC1AAE86","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112845$14DB712E-9963-4E24-8403-F7F13D95D6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112845$1F2AF553-4920-49DA-9777-06E5233F1DB5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea0d977ef0736516dc82a27b5a6199e36ade888a","datavalue":{"value":"4079477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112845$A3120296-0BD0-449C-AAC6-30130A633FE8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112845$36997A28-FD8E-4B57-A84E-1C082ADBA8DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bbb1088043ab5fbf02685384cb2a3ae983be6eb","datavalue":{"value":"graph recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112845$7344C8FB-E778-4717-9905-7FE851094952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32e1f5ad6148a7fecc64ae83f15fad7055a3ccc7","datavalue":{"value":"string graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112845$03837E85-92BC-4047-BA93-08F6995B3B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112845$687D1FDC-8D79-4EA6-A14D-E94A776E3B4F","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":"Q1112845$5AE66028-4678-494C-B3E7-511C832CB514","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e584cb82f13d31f8a03a6c13bdb408e1c093f86","datavalue":{"value":{"entity-type":"item","numeric-id":1234300,"id":"Q1234300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$1E87C31A-F969-4A9B-9DA5-A02AACA97400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff7677c8823f961be1caec5b996508c8f1452da5","datavalue":{"value":{"entity-type":"item","numeric-id":1572015,"id":"Q1572015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$9B0BD8BE-BB27-4164-A806-AD084289025F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c782da8cc8edba3e988eaf1db2b9c2a33d97f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3309881,"id":"Q3309881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$F12C6C37-AD9E-4775-BE0F-E7D9EFD04F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6890f0de4684848214a64aefe68fe2ed89d12b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3745859,"id":"Q3745859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$312713F3-A484-4156-921C-A677183BBF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ff364f4a7f6451ee58329319f801b32c5860fde","datavalue":{"value":{"entity-type":"item","numeric-id":1121917,"id":"Q1121917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$B3E15DB2-2502-4529-A081-04CC8FA64175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d901276bc7ac785f5a216e4482ca42f03c5458a","datavalue":{"value":{"entity-type":"item","numeric-id":3969882,"id":"Q3969882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$E035277A-791D-4191-85DC-CBF81F512299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e666d43d8a517121692b5641daf0b3ee081d310","datavalue":{"value":{"entity-type":"item","numeric-id":3821580,"id":"Q3821580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$196F0B64-3F18-4FF8-AEEF-2A1363652DCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$E50D47B8-8F8A-4220-83B3-167E5375A0E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56ab210fff5d79b2e4d4ad18f1a46804c4d49944","datavalue":{"value":{"entity-type":"item","numeric-id":1410732,"id":"Q1410732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$BEB7704E-2A82-4467-8ED5-5808628288D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2988b845f9f26b26a2975f2631350fdbb3d7c2","datavalue":{"value":{"entity-type":"item","numeric-id":5521330,"id":"Q5521330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112845$5AA9012B-0FBB-452B-9424-B299101612B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22d9f399ae292852db0c9f17eefc09edbc25235e","datavalue":{"value":{"entity-type":"item","numeric-id":5917583,"id":"Q5917583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aac72a432e429b7821b4265c65c3d7b01e95176","datavalue":{"value":{"amount":"+0.95350385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$F64954F2-7119-466B-A6E1-859307D2D439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8d84b3bc77f58ea215b2f673c66195e3f8c52bf","datavalue":{"value":{"entity-type":"item","numeric-id":3043722,"id":"Q3043722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee3c90b8af538e19f6a64e768c03fb354a779740","datavalue":{"value":{"amount":"+0.91729033","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$F8C52B3D-7DFC-48CB-AE85-6BFD640FC58E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bd8159dcc5e949c702d6668ff9b938b2896299d","datavalue":{"value":{"entity-type":"item","numeric-id":1864118,"id":"Q1864118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09558362761c34c61acd3b9de8d4247a0d03884b","datavalue":{"value":{"amount":"+0.9172902","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$0F5DDDF3-05CB-4F96-9E8A-6B0EB9389A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3ae609ba7984e00b5e98751c54ed5e7c80bba93","datavalue":{"value":{"entity-type":"item","numeric-id":5175975,"id":"Q5175975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e10424f243fa39bb18c45fc2a1e18e184bd664f6","datavalue":{"value":{"amount":"+0.8795912","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$51E463C6-64A2-4A46-9A68-3349ED844CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e1431edc563586f8bda6e15921c051f86c3418f","datavalue":{"value":{"entity-type":"item","numeric-id":1887714,"id":"Q1887714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e10424f243fa39bb18c45fc2a1e18e184bd664f6","datavalue":{"value":{"amount":"+0.8795912","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$D71DA20F-12AC-4F98-B68D-1458CD920FDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b217fe2912a1eef916a98c13092ba2c23c5dd78","datavalue":{"value":{"entity-type":"item","numeric-id":5091210,"id":"Q5091210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c48834e96702ebb48de2fe5bb6817bade3cb93b","datavalue":{"value":{"amount":"+0.8782692","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$959CE4D8-3C36-4DA3-AD95-E007949E7199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1384f47cb222577f6a60643d6083e336c2cb4a97","datavalue":{"value":{"entity-type":"item","numeric-id":6075757,"id":"Q6075757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c48834e96702ebb48de2fe5bb6817bade3cb93b","datavalue":{"value":{"amount":"+0.8782692","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$659154EB-50CE-4FDA-911E-D596A31E35D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eac7f804ae9ecd24fb62c8cf9ac9c1fc8364b98c","datavalue":{"value":{"entity-type":"item","numeric-id":5891424,"id":"Q5891424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed28740730cf02c6136235c05c716093078772e5","datavalue":{"value":{"amount":"+0.87132275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$EA400BF8-6B7C-4972-AE53-B2044DFF59AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb12bff30a9cbc4785bab7469da694925076b7a0","datavalue":{"value":{"entity-type":"item","numeric-id":5891657,"id":"Q5891657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed28740730cf02c6136235c05c716093078772e5","datavalue":{"value":{"amount":"+0.87132275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$36021A04-7206-4F5A-975A-213ADC3DE6DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bb8e80c908428cbf25c7177462e46ede3e204e9","datavalue":{"value":{"entity-type":"item","numeric-id":918697,"id":"Q918697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12390838838ef3d8293b1f6aab1c281e9b997a55","datavalue":{"value":{"amount":"+0.86317873","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1112845$A0A4C19C-0ECA-45E0-B364-72E9FA2F5DF0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1112845","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1112845"}}}}}