{"entities":{"Q5918671":{"pageid":8049601,"ns":120,"title":"Item:Q5918671","lastrevid":55407811,"modified":"2026-02-17T15:47:52Z","type":"item","id":"Q5918671","labels":{"en":{"language":"en","value":"Deciding whether a grid is a topological subgraph of a planar graph is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7515210"}},"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":"Q5918671$8D48B9E7-0893-4A88-B7E8-F06C6AD8AAC7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"65eb78887c4be129af3ba56e4ee86f133f52409b","datavalue":{"value":{"text":"Deciding whether a grid is a topological subgraph of a planar graph is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5918671$03D27229-E623-496D-8F18-A10B448A0B74","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bad65cf7a5a3a9ec0311b1276c0696f02700434","datavalue":{"value":{"entity-type":"item","numeric-id":299046,"id":"Q299046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$B34798C7-42A8-4B5B-96B8-CB5D629332F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac4b39357bad5e5d0a6b3c49bd81a5d22b345260","datavalue":{"value":{"entity-type":"item","numeric-id":322300,"id":"Q322300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$A73439C8-ABA6-4A1F-AD6D-5C38640A9A3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3478ec308a15597e43cb648673c843463f4d3028","datavalue":{"value":{"entity-type":"item","numeric-id":163528,"id":"Q163528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$E24F9276-A35A-484E-9D13-48E425D41155","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb92150f4e7ba6ad94427d659f8564387023a05a","datavalue":{"value":{"time":"+2022-04-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5918671$A834F14E-DC9E-4FC5-B6E4-AA9F2A5085ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f1a97a7188d4143e338e99eba7d65493911702cf","datavalue":{"value":"05Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918671$5026743A-2D2A-4B3E-BB3A-FC01BACC9EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"30e0158d39e8dcc6ee00ca7b3ae626e5899d5903","datavalue":{"value":"90Cxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918671$B6473582-F57F-445D-B696-7424D6047F10","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c1803639f1646122fc2d6d0cf628351bfa54d5ec","datavalue":{"value":"7515210","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918671$D3B3D900-B250-45A1-8E4C-4BA956B01AA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ccae32c54aacb5d15235438130f90cb8942e1df","datavalue":{"value":"topological subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918671$E78F9C1B-6F1D-4F3B-95F1-7DD264D40EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"745fbe54a7c9a755d76ba79942a85f557bc0d104","datavalue":{"value":"subgraph homeomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918671$837E2BD5-239B-4612-8933-EED0FBDB30EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d959bd733318746098f9611a2534b0fcaba0c1f","datavalue":{"value":"subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918671$8DF6637F-FC95-4E18-9AD1-35AB9AEB5D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f7b4330388d7b99fc9d918a33ddb2093f78f62b","datavalue":{"value":"grids","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918671$325D45B9-8A14-47BE-BA62-7BA773E10C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918671$A0BB5806-BE76-42C1-92B8-A97C0E2DD4E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918671$CA182260-9C7C-46E1-AC62-1A9CAD3A2CC6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f534699b7e60e4ca1f9f5216495560a7a5d70cc1","datavalue":{"value":"Q113317382","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918671$76D3A79E-F2D9-48F9-8B48-48AD6392A1F7","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":"Q5918671$A86EADE0-84A7-45F8-A381-923E4C86C5F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"03cac663237e0045cc9ed56bf612987f6f335a40","datavalue":{"value":"https://doi.org/10.1016/j.entcs.2019.08.048","type":"string"},"datatype":"url"},"type":"statement","id":"Q5918671$EF82CC10-92A5-4FA3-88E3-5FC3B7338749","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f77f0c04ffad4aa57270ce79ecf78e0bbb27e96d","datavalue":{"value":"W2978333103","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918671$3025B1EF-7F9B-4F4E-9D7D-343A8C83ECCC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"491950cd634035e7fd95f4062271456f77492b49","datavalue":{"value":{"entity-type":"item","numeric-id":1062457,"id":"Q1062457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$9B418EF3-2C49-4E7E-A05F-87FDE8A19FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eb31e432360eefb861cf6b39f872e00ebb2953b","datavalue":{"value":{"entity-type":"item","numeric-id":3578320,"id":"Q3578320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$1C96D8BF-FE2A-44E3-859A-A45116CAC18C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7966059b8174c3e66ce2fd2897328c574d917f4","datavalue":{"value":{"entity-type":"item","numeric-id":1117247,"id":"Q1117247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$69D391A7-873B-4204-85A4-7776CF32F113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$7020AEC4-E900-4681-BB51-2088C7E52B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4ce94fd036d8df30174fe6ce726c33ab9a507c","datavalue":{"value":{"entity-type":"item","numeric-id":5419118,"id":"Q5419118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$B52A56C5-8544-4CCF-8AED-A09E2DD3E3B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"150a26ef3a1250fe9beea92923122e9b6037420d","datavalue":{"value":{"entity-type":"item","numeric-id":1137871,"id":"Q1137871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$F8B4B883-8B1F-4DA8-BCB0-09A8A7A68167","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":"Q5918671$A1C89C72-2982-4137-8BF5-9B5B031E8BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6e526dd6b707e8c9782b8299d1783e64526ac62","datavalue":{"value":{"entity-type":"item","numeric-id":1031873,"id":"Q1031873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$779CE500-A0E6-4677-886F-B5F88718A4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5229eefbc7fd573d59f1b1ef9757b92d1905384e","datavalue":{"value":{"entity-type":"item","numeric-id":2449159,"id":"Q2449159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918671$5205AA25-00E3-411B-8B7B-CFB895DC2860","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d320ca8d4069abb1dac8ac159812a9f6115f46a","datavalue":{"value":"10.1016/J.ENTCS.2019.08.048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918671$F8CAA18A-7B83-4353-9356-71C17F9F9AC8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fcbd7008bd25071f6ec68d0d44aba7ff5469987","datavalue":{"value":{"entity-type":"item","numeric-id":5896079,"id":"Q5896079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbf768d7c91ddc838a39f39921f9409b1e6b7f8d","datavalue":{"value":{"amount":"+0.9944326281547546","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":"Q5918671$887B8066-96EE-40F8-AAF6-9C65FECB9375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61de15346e8d74f5d8f6acb346840d2c6922f92","datavalue":{"value":{"entity-type":"item","numeric-id":533881,"id":"Q533881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18f9ca278bd1606bc0b5ae221e7b5a9e803e2078","datavalue":{"value":{"amount":"+0.7665879130363464","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":"Q5918671$9B40F155-AB49-4DD2-AC03-7C4A97CE9DD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b417319b8dbc06d4ec41f42153fe7c94065a99b","datavalue":{"value":{"entity-type":"item","numeric-id":1920126,"id":"Q1920126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"050e9f9a1109841e94e6cf7066a66c48349d3ca1","datavalue":{"value":{"amount":"+0.7244734764099121","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":"Q5918671$D3321218-9BB8-4C0B-A3A9-3E43F0752A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"948819dccce731d5e1b1062f42e5a60dfe483da0","datavalue":{"value":{"entity-type":"item","numeric-id":5115795,"id":"Q5115795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d5f73c799deaed71d4dfa8b17c125b77b55c21f","datavalue":{"value":{"amount":"+0.7101137042045593","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":"Q5918671$7AB174D1-9F70-48FD-9395-BC52038D0EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f10c1fa2ffe72e577ed6429be3d134c0d25fe2da","datavalue":{"value":{"entity-type":"item","numeric-id":5881549,"id":"Q5881549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc90c7890f7616876cb3d490ac3d22819d8d30a9","datavalue":{"value":{"amount":"+0.7095240950584412","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":"Q5918671$E3B41162-9D85-4FD2-9DAC-1BBD4D6F5EF0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5918671","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5918671"}}}}}