{"entities":{"Q2154093":{"pageid":2164836,"ns":120,"title":"Item:Q2154093","lastrevid":43610644,"modified":"2025-10-28T14:58:30Z","type":"item","id":"Q2154093","labels":{"en":{"language":"en","value":"Finding geometric representations of apex graphs is NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7556569"}},"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":"Q2154093$7A2D2408-65DE-4F94-9007-070E4413D8FB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35d12070040e1d6789324bf57d4cd0ec45fb9fc3","datavalue":{"value":{"text":"Finding geometric representations of apex graphs is NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2154093$74CEEC21-3020-4785-A56F-3AC60901905A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b531fb5bd9017fd1fd0ad1a0f49e95a48d90994","datavalue":{"value":"10.1007/978-3-030-96731-4_14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2154093$B9114A8B-12D6-45C4-B1C6-5A9E706CC37D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b1a48ddc2fd7ed333ca9e119106bef682aecda6","datavalue":{"value":{"entity-type":"item","numeric-id":778516,"id":"Q778516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$AF298CE3-E57E-424D-B31F-B14923BB8161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a2dabf158da87097fea4e64c785cd5bbba89cbd","datavalue":{"value":{"entity-type":"item","numeric-id":2140501,"id":"Q2140501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$3EE23858-624F-44F6-88D8-3EB0C41CCD58","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5a10feb846ab08eff879cd9ad8918c74f60818d7","datavalue":{"value":{"time":"+2022-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2154093$6733EB57-DCFC-4CD6-92C9-B38541C06F75","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"64a7f5b88d08d43d00dde5dee69fc7ed4fb5f008","datavalue":{"value":"https://arxiv.org/abs/2104.09976","type":"string"},"datatype":"url"},"type":"statement","id":"Q2154093$B55BF45E-5557-488F-8C60-D5BAB0C121D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2154093$5EF4EA85-5618-484F-831C-188FF4F87C0C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63b1bdd3dd3d56bdc374ea46add5077b0e9d008e","datavalue":{"value":"7556569","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2154093$128B14A4-5BC8-4300-ABE4-3BB3F43F59D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$82856932-04DE-466D-B4F2-4F25323C88CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$A0707892-0C4F-4E0B-A5E2-AC9E5F298AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4ebf144833d0fac14993783a46bd6bc30f048e2","datavalue":{"value":"apex graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$A18F9232-B8C7-486A-AF57-C6CA1CC2BB93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe6ed001f3741ea122510955196ab0d25a033071","datavalue":{"value":"\\( \\mathsf{NP} \\)-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$34FC1B12-659F-4A5F-BEB3-ECDB4A07CD61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51c0410216f6db1f0aaf7ec78f4b1eb7c20b723a","datavalue":{"value":"recognition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$C34FAA2D-8F8F-426D-89E6-B44D58F05C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f4e568bbff651b0198406f59b3c0e72c01c516d","datavalue":{"value":"geometric intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$F6BAFB8C-CEDF-479B-A7FD-A62B06A3A436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38dd5c31d373d76e6308be0f17a0875fd182b166","datavalue":{"value":"VLSI design","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$EA438720-341B-4379-833C-EF5388974BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a23b5b99e91230b04d30ed0a3665fc2457cfe66f","datavalue":{"value":"1-STRING","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$CAC2315A-6AC7-4315-B331-C3B70F81777D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43c99cf5921c1b630e71bc40da59356edbd01e2e","datavalue":{"value":"PURE-2-DIR","type":"string"},"datatype":"string"},"type":"statement","id":"Q2154093$8BADDF99-214A-4A16-A96C-46C43DEEC99C","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":"Q2154093$3758B2CF-7216-42AE-BC6B-490A307DCF9E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"77c9d5fc155fb68d33025ab627328d70d56b1ecd","datavalue":{"value":"W3153542555","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2154093$D7C6566C-67DA-4BD2-943D-8457F20A2D85","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f081b612370b4d89ac4706c68841a63bdd940f3","datavalue":{"value":{"entity-type":"item","numeric-id":1276946,"id":"Q1276946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$214CA856-960A-4463-B3F0-401D8A26781E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b0322c4e2f2fba198fae73d0a70f8edd71a892","datavalue":{"value":{"entity-type":"item","numeric-id":5621735,"id":"Q5621735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$7ED8FB66-A0C4-42F2-89B5-30D1834B2084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ac3722bd2dc6d9df29ec050dfb84ffdcf8f036","datavalue":{"value":{"entity-type":"item","numeric-id":3104763,"id":"Q3104763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$878F8662-3F25-4EE9-B8E6-088ABC39B017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2860b21ec28091243d6f8b5601ce1d563a55934","datavalue":{"value":{"entity-type":"item","numeric-id":1136775,"id":"Q1136775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$88CC411C-D72F-4976-A802-C14118AE6A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$5A03E583-FE30-4B01-AFBA-87A005D7F46E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acf57164837f6e57ac1f33469dc87a6151556561","datavalue":{"value":{"entity-type":"item","numeric-id":2959779,"id":"Q2959779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$80F4A2E8-879D-483D-920A-9CC63CC2BC49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4a381dce4100bafc346fa18a9f4f26641825a6e","datavalue":{"value":{"entity-type":"item","numeric-id":1384186,"id":"Q1384186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$F4B0FD2F-0F2B-4D28-80A7-E2A066662F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02fde088d9f344dbc6e48254d228b0fcaa50fa84","datavalue":{"value":{"entity-type":"item","numeric-id":5172758,"id":"Q5172758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$E0CB5AC4-EF01-426A-ACF4-5119C408DEF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b8e3aa37800131df30fe84ea70b75b4f77f5e44","datavalue":{"value":{"entity-type":"item","numeric-id":2380780,"id":"Q2380780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$A92D3BEC-D933-4368-94A7-901B2C72D8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6bc19109f9086a42fa917c99b406b0583a19365","datavalue":{"value":{"entity-type":"item","numeric-id":5200514,"id":"Q5200514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$2213E861-35A8-4073-AC38-89A46FDEEBFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8eb5d4554fd2f095a2669c598f28f50aa8e7dcc","datavalue":{"value":{"entity-type":"item","numeric-id":4501713,"id":"Q4501713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$67F07D63-893B-462B-B49A-0DE097628C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$67B8FD8E-E394-438D-BFBB-F14BD3A701E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1169ec8b0519f98549638aa213bf4c3ac0471505","datavalue":{"value":{"entity-type":"item","numeric-id":2042057,"id":"Q2042057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$77209465-DA31-4A80-9455-2AE76A02086C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a21640ed12e71fdd148aa5a907de7ecfffc2b30d","datavalue":{"value":{"entity-type":"item","numeric-id":2301556,"id":"Q2301556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$E3C6B109-A168-48DD-8091-478B8F302235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4281c743bd23d6098b8e639a3e85e4030216d6c9","datavalue":{"value":{"entity-type":"item","numeric-id":5119380,"id":"Q5119380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$429ED457-4CFC-4873-B28D-A489C9267171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e29825f11ef39564bc0bc49e7feedb310940d67d","datavalue":{"value":{"entity-type":"item","numeric-id":4607888,"id":"Q4607888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$6106DD48-68EE-43F0-AFB5-A2957E6AA7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c03169bdd15b03b38cbc5b3e03b5fd91c559457","datavalue":{"value":{"entity-type":"item","numeric-id":5240366,"id":"Q5240366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$CCE8063A-106A-4B83-864F-C41B4E196D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9b140abc3379335beff4b6ba5f945f9c277d40a","datavalue":{"value":{"entity-type":"item","numeric-id":1174140,"id":"Q1174140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$6425774B-E80B-43A6-9D1C-69DC88C6B619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e79ca683df5d5a7781157d0027eb4b908505a34","datavalue":{"value":{"entity-type":"item","numeric-id":2959776,"id":"Q2959776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$46A2C567-7086-42A0-979F-1A9D8C0B3917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac9a0e7ebed83e72d9b8966739b88f8b43a3f5d8","datavalue":{"value":{"entity-type":"item","numeric-id":1112845,"id":"Q1112845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$7E51424F-5E25-499F-8A28-FB98001E2DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1152bc7463fcce9eed8b94a2712374316ad80364","datavalue":{"value":{"entity-type":"item","numeric-id":1331895,"id":"Q1331895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$117C7615-24C7-48B6-B7D3-D2DDB401631D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d778db789e2f0c4036a8212e45cdf87ab994ed","datavalue":{"value":{"entity-type":"item","numeric-id":3474685,"id":"Q3474685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$FD529932-828E-46F3-AC10-FB2A6B5C74F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ed43ffd193b725756b8b8d46ca58e4700f341bd","datavalue":{"value":{"entity-type":"item","numeric-id":1338319,"id":"Q1338319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$4C927787-FC57-4C33-B8EB-1851DC6D98AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d483f8478d9f0fe07677a048f8886fcf31803162","datavalue":{"value":{"entity-type":"item","numeric-id":3608838,"id":"Q3608838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$0B443888-0BBF-4A01-8C84-CDF817AC8E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$BFEDCBB7-8A8A-4E83-A9B7-436C9E519AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"248729ebc4d6876ccf402d4746249e334c3f8ead","datavalue":{"value":{"entity-type":"item","numeric-id":705888,"id":"Q705888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$30BE0306-CD73-4044-922A-464A5411D4EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"692021b93719a66444e95ec965c53845c691daa7","datavalue":{"value":{"entity-type":"item","numeric-id":5917583,"id":"Q5917583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$F945C5C0-62A6-442A-BCD9-834C9B834C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b88bab3421c99c89eee00e18865ef0f3aabb08fd","datavalue":{"value":{"entity-type":"item","numeric-id":4850027,"id":"Q4850027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$A41E94E7-FFA4-4BDE-BA58-77356ADA2307","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":"Q2154093$A99A0122-486F-4C3D-9CD8-3C06A29B989F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42ef78a9e5184a70ad2e2377f0b50263aff3698f","datavalue":{"value":{"entity-type":"item","numeric-id":287003,"id":"Q287003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$002F7F6A-1D9C-4C3B-8655-E96223BC70A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"427f491595a6a752b0dbab7bb488a8b03f814419","datavalue":{"value":{"entity-type":"item","numeric-id":1077425,"id":"Q1077425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$C4E69D57-07BF-4716-82BF-63F1E5ED1378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2045fc2ff8eca1ca2de634cc5326b053a1e46920","datavalue":{"value":{"entity-type":"item","numeric-id":3942069,"id":"Q3942069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$A87CAB22-8F3D-4C9C-85E9-77B05C0CBC0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a207b31fa61009a063623eaec8272b572b4eb96","datavalue":{"value":{"entity-type":"item","numeric-id":4273837,"id":"Q4273837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$BB47430A-1D2A-4BB6-A77D-004570694BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e80a091f736092dcf2c7873b5d0007cb9e4e6778","datavalue":{"value":{"entity-type":"item","numeric-id":3546318,"id":"Q3546318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2154093$AD60CBDB-296B-46CA-8A88-8CE56CFB8601","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2154093","badges":[]}}}}}