{"entities":{"Q653839":{"pageid":655688,"ns":120,"title":"Item:Q653839","lastrevid":63352416,"modified":"2026-04-11T12:17:52Z","type":"item","id":"Q653839","labels":{"en":{"language":"en","value":"Algorithms for finding an induced cycle in planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990610"}},"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":"Q653839$EA74EC5F-719A-4CFB-8284-DEF0BC642945","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"75c1ecf217aebb36b517a62a1d73db2854c984f3","datavalue":{"value":{"text":"Algorithms for finding an induced cycle in planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653839$EE582E63-5695-4033-BE81-B3DE3F9F0D52","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e715f00ed8ac3c8732e9a4141a05c098a6a7928","datavalue":{"value":"1240.05291","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$D1271BAD-5C43-429F-8E83-2F1C98BB3F0F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd4984510ecb87e1198d778e5c81672940646bc6","datavalue":{"value":{"entity-type":"item","numeric-id":273162,"id":"Q273162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$5E4ADCF9-FEBB-471F-A7DA-E67C61A00A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f4e7bb5eb3d92423af4c11d1172a2aa89ed8c8c","datavalue":{"value":{"entity-type":"item","numeric-id":214979,"id":"Q214979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$88C83085-6F91-43D4-B28D-D0008B1AEA3D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$25753AB3-722C-4603-968E-BA54016DA7E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e7c33876f49da64580f033b95b71f550b669c2d","datavalue":{"value":{"time":"+2011-12-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q653839$32256D3C-2BAD-4168-B335-A51E98CBA7FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a71f5ddfae6804507ef11b8a94825cb29345cd9c","datavalue":{"value":"The induced cycle problem consists of finding an induced cycle, i.e., a cycle without a chord, passing through \\(k\\) given vertices. This problem is NP-complete in a general graph. In the paper the authors restrict themselves to planar graphs. For them is is proved that if \\(k\\) is fixed then the time complexity is linear. On the other hand if \\(k\\) is not fixed but \\(k=o\\left(\\frac{\\log n}{\\log\\log n}\\right)^{\\frac 23}\\), where \\(n\\) is the number of vertices, then the induced cycle problem can be solved in \\(O\\left(n^{2+\\varepsilon}\\right)\\) time for any \\(\\varepsilon>0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q653839$4154D4C1-8A56-4539-BE48-AE5433E3D78C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$DB055C25-8ECE-4358-9C71-09671EE509CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$85C16785-D9C2-4075-87F5-DB53B3C8C7E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$C3EE6365-8E0A-4F74-8BB2-62ECD2FCDAE4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2cbace32bc30f02112dc4b38e5ade02271ea73ed","datavalue":{"value":"5990610","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$3FCED169-D9FF-4A18-84A7-BE99510AF6D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q653839$59B1E7DF-016E-4C61-BED6-DECD4667B3D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q653839$61B58836-076A-4BBD-A4BD-85EC6BF874A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94ed6885a1ca21bebabd977bf75106246fc53489","datavalue":{"value":"induced cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q653839$0435E3E1-0B14-454E-9D26-FFEF930220BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41378e6e6b23146743ebdfedd46f11c4ac89fa1a","datavalue":{"value":"hole","type":"string"},"datatype":"string"},"type":"statement","id":"Q653839$3F619729-0217-4B14-BDBC-01EA07D960E9","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":"Q653839$5522C789-6377-49C7-B92C-000DAD9DF5A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a233f54c3a99897363a0fc30f63dcee0245d8f66","datavalue":{"value":"https://doi.org/10.1007/s00493-010-2499-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q653839$4B71DBCA-9C89-4BA3-B179-19030FFD4C43","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"31a2df64cfe956a67ca4f00b3c1b736444b04b75","datavalue":{"value":"W1989836886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$1F69810F-1AA8-450B-AA3D-223D8FBB3919","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$9CC87AF8-A401-4B2C-A853-F7F4CA5B85E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82cfa9f684c3350648874deb95288407da9381e","datavalue":{"value":{"entity-type":"item","numeric-id":1175980,"id":"Q1175980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$B3004DCD-B9B5-4047-B36F-231791DA9A23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$2B54E040-4B95-4BF0-8C9F-4FED5337FC8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20e0b8b69bb74bc107c5a48305e78f34c64cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$24B54384-02EF-48AF-8F98-0F2FBF7DDC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68256ced5293cf8202ccd95f7beb5cd21a8eab7a","datavalue":{"value":{"entity-type":"item","numeric-id":4667791,"id":"Q4667791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$FB977434-6EA4-4FD8-B0DE-7279920E1691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$E7F525A8-A6B6-4072-BBB8-AC20D0FCCE4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a864a6dcd2e24a55e0641da1a8bb1c0d7272cc","datavalue":{"value":{"entity-type":"item","numeric-id":2778281,"id":"Q2778281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$1CD1FBAC-F7E3-4640-AAB0-C01ECB3515B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40db7978f2fa4f72a9fc47f33a15ad28a0b78f1a","datavalue":{"value":{"entity-type":"item","numeric-id":3150171,"id":"Q3150171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$33C1A72A-E4F7-47F5-9CF8-DE5C59A594D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8841424a46c2ac3531bdba4734ffccd1a754c5ca","datavalue":{"value":{"entity-type":"item","numeric-id":1346772,"id":"Q1346772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$0EA26A82-C7C5-4E77-A021-2403A363A4C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c291cb4684d45d852c1e6bc09e80871cd583a8e","datavalue":{"value":{"entity-type":"item","numeric-id":414938,"id":"Q414938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$BEFD191B-B22A-44CD-B854-645CE94D8E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02980cf4411eb7f6e0f0dbda88fb746e9b54abf0","datavalue":{"value":{"entity-type":"item","numeric-id":3503839,"id":"Q3503839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$5F450338-C14E-4704-93BD-C64BC782C74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e8bd22897cb07a4ff52fcae17d00f8dfcec5ee6","datavalue":{"value":{"entity-type":"item","numeric-id":967379,"id":"Q967379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$57821AB2-A476-4EBD-8D71-0DA26F7F86F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9844275a4fad6a2b4a6642f67a0829d6ecd0268d","datavalue":{"value":{"entity-type":"item","numeric-id":1322013,"id":"Q1322013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$0617373D-4C10-4F02-A550-BCDAF3A56234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9799935fa6b5975808f92cfcc703600c2e6e3c88","datavalue":{"value":{"entity-type":"item","numeric-id":2726740,"id":"Q2726740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$D4F13921-E6C8-441C-A876-8F8982E887DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83abc54ec7933ecbbf60cd7bbe5af0ddd06f4803","datavalue":{"value":{"entity-type":"item","numeric-id":1346696,"id":"Q1346696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$481B9107-568E-4106-94CF-0B4DC1861BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f60d2c85059e8c02a466817a5352aa84c623bfd","datavalue":{"value":{"entity-type":"item","numeric-id":4273851,"id":"Q4273851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$6D271CC0-5FDF-44A2-99B8-8B13A31021BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f269220351fd673e9f0e861c3726f061e24f60eb","datavalue":{"value":{"entity-type":"item","numeric-id":1111568,"id":"Q1111568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$02B94A0C-BDEB-49DE-8AC6-21934E65D57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bc610dcd70b16f4c896d3d7b685fb0f39b6b990","datavalue":{"value":{"entity-type":"item","numeric-id":1322009,"id":"Q1322009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$429A3AFB-71EA-4841-B464-82A1C27AB075","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":"Q653839$E7A4B53C-EAED-4067-AAA9-CD2E58CB1CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad6cbfc4f1ffe25e36693a2d38b9afdf54e56c18","datavalue":{"value":{"entity-type":"item","numeric-id":412177,"id":"Q412177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$5525AC8E-2D0F-46AC-9B35-24ED199001DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a583b336166cebbddf1ca439ee3458ed6982ce7","datavalue":{"value":{"entity-type":"item","numeric-id":1338321,"id":"Q1338321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653839$74932F8B-7E89-40E1-9F78-C8CB52F85AB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2ef6d029d1628f20327fbe841c0f77351cbbe40","datavalue":{"value":"10.1007/S00493-010-2499-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653839$34654565-B419-4D05-8762-2243F52FFA8B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"149099e36b1b4463c331ac2b1f3a89d03e2764c9","datavalue":{"value":{"entity-type":"item","numeric-id":4633929,"id":"Q4633929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cf9ce34423bbc1c16c1b989cdbcff84b8e55208","datavalue":{"value":{"amount":"+0.9101529121398926","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":"Q653839$DD1F156B-00C0-4338-A023-A3103705A98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14574d659e84f34e545e935f9d0a9fbf85646756","datavalue":{"value":{"entity-type":"item","numeric-id":1322013,"id":"Q1322013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38d010d5831f2b1bf85c41ed73cf1f00905dfa47","datavalue":{"value":{"amount":"+0.8540818095207214","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":"Q653839$93258FA2-283F-4139-9706-856DAF2F4796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a65cb743cfcced13fc1b94b96179123b8fb66a3d","datavalue":{"value":{"entity-type":"item","numeric-id":2494820,"id":"Q2494820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0837af94d006304538762a7222982339397a08cf","datavalue":{"value":{"amount":"+0.8531323671340942","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":"Q653839$2AC8C258-29BE-4455-B234-D9CF772E4895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d231b4752fb704262314300ea21c163e96ed219","datavalue":{"value":{"entity-type":"item","numeric-id":5743428,"id":"Q5743428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2cf316637e3f2e2a64f4981428e48a152d5d5e3","datavalue":{"value":{"amount":"+0.8077817559242249","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":"Q653839$4B828CFB-E9CE-4A3F-A650-90CC331199E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00fac9ac31e41cd16efa959e297aea125673af08","datavalue":{"value":{"entity-type":"item","numeric-id":3092237,"id":"Q3092237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69b912cbe056058919dfff3d8cf0c62aab31e32b","datavalue":{"value":{"amount":"+0.7997235059738159","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":"Q653839$58C40D7B-63FB-4A56-887E-EFF8B3306B6A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms for finding an induced cycle in planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_for_finding_an_induced_cycle_in_planar_graphs"}}}}}