{"entities":{"Q1962068":{"pageid":1972810,"ns":120,"title":"Item:Q1962068","lastrevid":47437360,"modified":"2026-01-01T18:17:03Z","type":"item","id":"Q1962068","labels":{"en":{"language":"en","value":"Pancyclicity and NP-completeness in planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395033"}},"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":"Q1962068$EC3BCC0B-95AD-4E04-946D-2CD82032CCCD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a98c47c96c031367d80e09e369fbc2a3c3664aea","datavalue":{"value":{"text":"Pancyclicity and NP-completeness in planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962068$DFFECB74-6FF8-49E5-8090-29A1A54652AB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fb34fad5229bd27be90b2474ce2467fb25603208","datavalue":{"value":"0939.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$C9C8E7E0-39AC-433F-AE4D-7CDBDA57CA1B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e44d53eb34ccf0f7ea6db6cd0c576e530abd5c7","datavalue":{"value":"10.1016/S0166-218X(99)00163-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$66DF140D-CE8B-4B02-A773-E3EFFF701812","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6e069632bd64571bdb3688b445bcf608dea524a","datavalue":{"value":{"entity-type":"item","numeric-id":306348,"id":"Q306348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$A3118D1B-B4A8-452F-94BF-BCF2BBE7ED9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"792838b4debdd7e9544aeef506080e0b950295ac","datavalue":{"value":{"entity-type":"item","numeric-id":1666749,"id":"Q1666749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$B2B081A2-4BA4-4DFF-A47C-58353F329FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eac3bc3b952de30e0dbd044a5b978d4bbca81a36","datavalue":{"value":{"entity-type":"item","numeric-id":1070246,"id":"Q1070246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$2A035759-BD77-49A9-825C-4DDCE68DDCA2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$0BCD0323-2231-411A-B0CE-C8114058679D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a607f304712b79d2eec9848961c4d4b0d86f1fee","datavalue":{"value":{"time":"+2000-06-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":"Q1962068$37FFD104-FF43-4DE4-97A3-3141744AD044","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c4657ff1ae6e8bace56839985f2d462145888426","datavalue":{"value":"A graph is called {\\(v\\)-pancyclic} if it contains a cycle of length \\(l\\) containing a given vertex \\(v\\) for \\(3\\leq l\\leq n\\), and a graph \\(G\\) is called vertex pancyclic if \\(G\\) is \\(v\\)-pancyclic for all \\(v\\). The authors show that it is NP-complete to determine whether a 3-connected cubic planar graph is \\(v\\)-pancyclic for given vertex \\(v\\), it is NP-complete to determine whether a 3-connected cubic planar graph is pancyclic, and it is NP-complete to determine whether a 3-connected planar graph is vertex pancyclic. They also show that every maximal outplanar graph is vertex pancyclic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962068$BA42A983-1ED6-425F-BAE2-26D2ECC71F59","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"094d61d1ff99e208b2511ef0c6fc952ca4052a28","datavalue":{"value":{"entity-type":"item","numeric-id":230778,"id":"Q230778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$A5768531-2902-48AD-88F0-32CD99FF50FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$AFA13145-9AA8-43A6-9C8B-D2A29BAC1B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$D4EB69FC-A09B-4599-86A4-AAAD70D025DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$11B32372-017E-4349-93BB-E3356315F57E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$640957B2-53ED-4CBD-8037-9F491512821D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec0b10e09a681ac2e2fe2a862893963af121be9f","datavalue":{"value":"1395033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$80C5499A-8D40-466C-B2E4-8C8C1FABBF12","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962068$0AD8B884-25AC-46FD-959B-1FAB1DBB66D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962068$165681B3-86F8-4B06-9012-38E55DF46612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a581547e73ad9d5fbfe71e12b8a9a165e12ce39","datavalue":{"value":"vertex pancyclicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962068$BAF85136-96F7-4437-B0F7-1C58CA5C4EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962068$CF5A79FF-96B5-4F12-99B0-C18EBCF97316","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"65debf21764899163ca9e999caa60cd1fc15c6ff","datavalue":{"value":"Q56235005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$A8AE606C-A317-4A55-AFAF-00A1BC442030","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":"Q1962068$F86658C6-0996-4E17-BD66-1F04316A7006","rank":"normal"}],"P223":[{"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":"Q1962068$AA41F0A1-95D6-4714-8726-61C2034FB6BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$35FB0A43-8D26-470E-B00E-7BB9D539E453","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ebb1a57b2da0ce9ac5b38761a444432e3f6adb0","datavalue":{"value":{"entity-type":"item","numeric-id":1227753,"id":"Q1227753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962068$21E146EE-F8EB-4D94-871C-01E2ACBE532B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"618e7a473855d0711c1609bb200b964a48305628","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00163-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1962068$3FEBEB03-37B2-4CEE-B307-F2819F46B2A4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e7911a87831190711048ea6e702aa6457407faf8","datavalue":{"value":"W2008914847","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$216E6B9E-7529-4FA4-A2CA-F4D0182296C6","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"8ff074ca6903c174ad86485d5ab706e192f9c29a","datavalue":{"value":"journals/dam/LiCM00","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962068$15ACB12A-87B0-4449-B6AD-3923ED95829D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1681343d10adbda5b503edce950d7a7c10d1e24a","datavalue":{"value":{"entity-type":"item","numeric-id":1613376,"id":"Q1613376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c84aa560a4b421185ab40bf43a230aeb1dd96ff5","datavalue":{"value":{"amount":"+0.7842890620231628","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":"Q1962068$3DE9DDD4-86C0-4D42-A778-DEC8F46C36AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"921d96a242bdc6fa7273488b44e2e4b059175d98","datavalue":{"value":{"entity-type":"item","numeric-id":4529496,"id":"Q4529496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d77140e920439df6894d08a45330014aa6139506","datavalue":{"value":{"amount":"+0.7804855108261108","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":"Q1962068$8A409816-792B-4971-88F7-0395DE4FF0CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0560183c1366286427f22c8288ae85076fff83d6","datavalue":{"value":{"entity-type":"item","numeric-id":4873814,"id":"Q4873814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7965160b1f93d394d4bc9b4ad8c0a76cdff31305","datavalue":{"value":{"amount":"+0.7739002704620361","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":"Q1962068$2CD6B773-20A5-47E6-A510-E349607629AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19887650d06c6fe6d516ae51146fb6c9ac0873dd","datavalue":{"value":{"entity-type":"item","numeric-id":2741362,"id":"Q2741362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d0d94dea845aba2c9d5f05341cc5a81ae43eba6","datavalue":{"value":{"amount":"+0.7719748020172119","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":"Q1962068$98502FB4-84FD-4B56-8580-B779EF70BCE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc7a203e3d48628752ab581776b52cab67202d5b","datavalue":{"value":{"entity-type":"item","numeric-id":3325758,"id":"Q3325758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f81e2689825c10533e36687da49e8a7994f7253","datavalue":{"value":{"amount":"+0.7712168097496033","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":"Q1962068$47BFA722-D2F0-4049-B42E-EF547C9F8562","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962068","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962068"}}}}}