{"entities":{"Q2268858":{"pageid":2279601,"ns":120,"title":"Item:Q2268858","lastrevid":50923397,"modified":"2026-01-15T18:44:14Z","type":"item","id":"Q2268858","labels":{"en":{"language":"en","value":"NP-completeness of st-orientations for plane graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5678862"}},"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":"Q2268858$CD505E26-BC3A-4035-9A4F-7EA7C1D6B9CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"deb6b348041814aafed7aca60ff3c5f0f5f9a924","datavalue":{"value":{"text":"NP-completeness of st-orientations for plane graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2268858$FB491924-0B9A-4CB0-BEB6-2DE0FCD31F0B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"33de77284ff3be18ceaa7f50e247d2bd8f1e6ddc","datavalue":{"value":"1213.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$47EFAE32-0F29-4D67-829B-9D922CA44265","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fae642a7daaffdcfd4939793bdbfcc622942ae43","datavalue":{"value":{"entity-type":"item","numeric-id":411252,"id":"Q411252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$3CF40DD5-CA62-453C-80C4-2A246CC5A14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8fed5f8514cff6c4b404f06640e44b22716b7ab","datavalue":{"value":{"entity-type":"item","numeric-id":283867,"id":"Q283867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$2F4FE5CA-48CE-4B73-B470-C73356A925F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$EDA875A5-BD1D-4EF3-A533-A0E4A1119982","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"10dcb20d02ba2b80ffd27851e30b5d754f8113d8","datavalue":{"value":{"time":"+2010-03-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2268858$50321C4D-F26C-4520-BF7F-E47C3D504B30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$A9548614-8CCA-48C6-BE5B-D83197C3BE54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$0EF4F68F-9B92-474B-A304-EC54CCFAD453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$B179F263-6CF2-47A5-9904-AC0B1F8A31A3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4053cb4abd3a0b40fb1991a2ce6ca909d9308ca0","datavalue":{"value":"5678862","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$98DA5B07-6C10-45F1-85F0-2D85F76CC764","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268858$E8450324-DC4E-4612-A4D1-70B665931252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2557e79dc77cdc109c21515a28a556b4bf246896","datavalue":{"value":"\\(st\\)-orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268858$38D22F7C-D736-4FDC-8792-166ED7B1A073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66b1e6938a358c4d5326f21b74cba7bf515efeb7","datavalue":{"value":"plane graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268858$653E8806-85D0-4913-B23B-19BFAEF31FA4","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":"Q2268858$C20A93CD-64E8-48B3-947F-03B9365AA92E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f0444edb21f1ab2c37bf7b83ccd00a83df20109","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2009.11.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q2268858$AF16C110-2991-47FA-8FE9-5489FE9C7E76","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"171c354102e07054297cb6b7885ea33dbd2fc52c","datavalue":{"value":"W2047890727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$E70B6783-C75A-40EE-9743-D1C21451A741","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f6be2f565b9260a417ac143b35a648c330ea8c7","datavalue":{"value":{"entity-type":"item","numeric-id":4490784,"id":"Q4490784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$2F3203ED-985E-4D03-840D-5B811FAED2A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"625a03d46620a33bee2de786dbc5e81f0c26accc","datavalue":{"value":{"entity-type":"item","numeric-id":3154375,"id":"Q3154375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$721CADA3-8167-45AE-92D3-C6A76B7265B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$04C58BB9-AE28-47B3-9050-6E67A341ED23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e9482ac52774f29c3e0eabec830d52edd86da50","datavalue":{"value":{"entity-type":"item","numeric-id":1231771,"id":"Q1231771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$E189DB52-5A23-4BD8-AD3D-8F6EF37593FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bdd250a45275500c245c98aa669a4cad3fe76cd","datavalue":{"value":{"entity-type":"item","numeric-id":5545303,"id":"Q5545303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$A24DE76C-28C1-4864-AE88-689CE5E700DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7425e1620f2e0783fe0308bfce9fda966f4006bc","datavalue":{"value":{"entity-type":"item","numeric-id":4277538,"id":"Q4277538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$449A25D5-E445-4B79-BEF7-B18E3EB7ACCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7871dc2cc85bb5a8983590b741f23a06f01bacee","datavalue":{"value":{"entity-type":"item","numeric-id":5596083,"id":"Q5596083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$C7EF9E27-BD77-4762-A98F-87008853DE84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8647bb8bd68986766e0018d1458b2fb09ab20ec7","datavalue":{"value":{"entity-type":"item","numeric-id":287104,"id":"Q287104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$9E86DA1B-B0AD-4D7A-A447-276C00BD1391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6d04f819d33561d18482cdbafd125731d0693d2","datavalue":{"value":{"entity-type":"item","numeric-id":1384191,"id":"Q1384191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$7C4405BB-95D4-4FF6-B7DC-3A91AB265949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a041352acc952f3c51f809e1bf238fa32a8ddbfb","datavalue":{"value":{"entity-type":"item","numeric-id":5897644,"id":"Q5897644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$0A2CB460-6DEB-4842-9ED8-2052E25487BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d06da2ea2d383db4233e5c7c12977030ad76300c","datavalue":{"value":{"entity-type":"item","numeric-id":959815,"id":"Q959815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$AE4AFF8A-21C3-4315-9FE0-A70714751BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2dc51f455e8035861032dfb9491c0817f3e724","datavalue":{"value":{"entity-type":"item","numeric-id":1085168,"id":"Q1085168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$E3D6FECE-ED09-47F4-BD55-0B27C1EBD529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d559325bc6d150c41f7e7c490b2a619364a89614","datavalue":{"value":{"entity-type":"item","numeric-id":1085167,"id":"Q1085167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268858$3FC99087-EB0E-4245-A072-322D12DD1313","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb8dbd63adabc34eede5805efd12dfa910378d2d","datavalue":{"value":"10.1016/J.TCS.2009.11.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268858$64D00E80-F83F-4C23-AD67-1AD37E3E7C01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90b4851b1d14cce404188c1418197c7d3102b801","datavalue":{"value":{"entity-type":"item","numeric-id":3183620,"id":"Q3183620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c28c276a087cb00420fc754c9e852db6d79f3dbd","datavalue":{"value":{"amount":"+0.9937676191329956","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":"Q2268858$EE694B8F-9F22-4539-A4B5-219DDC8A880A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"405ebcbb661ea0a42820e5a0178308d7ff67fcc3","datavalue":{"value":{"entity-type":"item","numeric-id":3595466,"id":"Q3595466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ef3d434ace2d0bc53f29865f9b829134c067e00","datavalue":{"value":{"amount":"+0.7715077996253967","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":"Q2268858$8D01C7A7-508E-499E-BBA9-C7B75978725B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b67cfdaaa50fba24e987f22f628cc2c49d9a09","datavalue":{"value":{"entity-type":"item","numeric-id":412352,"id":"Q412352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b601e551c4cc3927fd93940947a35f7e1513da23","datavalue":{"value":{"amount":"+0.7676500082015991","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":"Q2268858$66579C84-260B-4280-AC08-0DF5B7F35850","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f50f45fcd95dff1edc1fa8718904be3fb384bf5b","datavalue":{"value":{"entity-type":"item","numeric-id":3561426,"id":"Q3561426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37570c8ddd20606ef8f7b36379dc4bde7455558a","datavalue":{"value":{"amount":"+0.7649986743927002","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":"Q2268858$75DEB9E2-5E67-4B96-B40A-A58B9DC33F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"850acba6d0071bd464daee705626c87f164462b2","datavalue":{"value":{"entity-type":"item","numeric-id":959815,"id":"Q959815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66397ded18da528cb726db06fc7fdf7c6bf8b9c3","datavalue":{"value":{"amount":"+0.762033998966217","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":"Q2268858$DDB6B62E-37ED-4541-8F21-B983A831F2EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2268858","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2268858"}}}}}