{"entities":{"Q1085169":{"pageid":1095921,"ns":120,"title":"Item:Q1085169","lastrevid":66103839,"modified":"2026-04-12T07:34:28Z","type":"item","id":"Q1085169","labels":{"en":{"language":"en","value":"Finding small simple cycle separators for 2-connected planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3981195"}},"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":"Q1085169$1B2C6E0E-DCBD-4A3D-AB4F-6EC694CB8229","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b3083047818f7db2a2edf261bbcfd66a058ed26","datavalue":{"value":{"text":"Finding small simple cycle separators for 2-connected planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1085169$23D8A9B1-BE27-4816-8F22-2FF666DC539B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"babd8ae691b55cacedcc1928c7a91ff1988d7b16","datavalue":{"value":"0607.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085169$EBF6579F-C3E9-4762-A166-5568CC4B7329","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"107f6607311e9d2455977890a89b397d841bccb1","datavalue":{"value":"10.1016/0022-0000(86)90030-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085169$7232E433-1B2A-485C-B8D2-D2E4841CF0A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"29373d22cc965afe0313777aac5867e3ef096150","datavalue":{"value":{"entity-type":"item","numeric-id":1071802,"id":"Q1071802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$5F244680-E655-4F3E-8F18-CF695B7D2F96","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$072641DA-19AC-49E3-80C9-B2CDF98FAFD7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1085169$C4A13743-A90B-4A38-9DA7-6355A9DFD4D8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"af929100a3fca22db4beef8dfed0515afaec4765","datavalue":{"value":"A graph of order n is said to have a f(n)-vertex separator if there exists a partition of its vertices into three sets A, B and C such that \\(| C| \\leq f(n)\\), \\(| A|,| B| \\leq 2n/3\\) and no edge exists between A and B. \\textit{R. J. Lipton} and \\textit{R. E. Tarjan} [SIAM J. Appl. Math. 36, 177-189 (1979; Zbl 0432.05022)] showed that planar graphs have \\(\\sqrt{8n}\\)-vertex separators, and \\textit{H. N. Djidjev} [C. R. Acad. Bulg. Sci. 35, 1053-1056 (1982; Zbl 0516.05051)] improved this to \\(\\sqrt{6n}.\\)    The author proves that for planar triangulations of order n there is always a \\(\\sqrt{8n}\\)-vertex separator such that the set C is a simple cycle. The method also gives a linear time sequential algorithm for finding this simple cycle, and an NC parallel algorithm. In general, if the maximum face size in an embedded plane graph is d then a cycle C as above can be exhibited, being of size \\(\\leq 2\\sqrt{nd}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085169$B9FCCDB9-DFEC-4545-8C5E-872F6630FF38","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085169$AEF7FB78-4785-4A75-B4B7-B9E2AE0A7CE4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2cad1a94424ba2cc21d48776218bac30d55077cc","datavalue":{"value":"3981195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085169$90D5012D-FCE9-4607-B6E5-CB16AD5D32FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"510e1196be7502530cb9e6947e1ea655a59ab289","datavalue":{"value":"vertex separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085169$B779C2B9-1CFC-4A7B-A02E-6AE22F093A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c402bbe4761407be2e036cd2435c81a0fc82915a","datavalue":{"value":"planar triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085169$73EF4132-849D-4038-A690-AB28BF2257AC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90c78b3265eaf03d2c9093f31b0f9730424156f8","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$59ABDD79-28F5-4C51-B88F-6F7EB467A947","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":"Q1085169$10A6D2DD-1639-4A57-A3C0-60F29C85D457","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d1671f79036a8160e91f7164f0bfa595a9a3b8df","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90030-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1085169$F7575BA0-8A77-429A-90CE-71427529EAB0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b1a16f09119a3cf4ec4aef00d969384c599b72d9","datavalue":{"value":"W2049413646","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085169$24F3698E-A410-4B7F-91CC-04B3F572E36F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$1B219B85-A857-4316-BB49-A407BB968CB5","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":"Q1085169$18C4F51D-1FD0-4100-BC8E-C0EC7FE15037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$EE5D4455-EDEF-47CF-AD66-55A5D8A6EC31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0f031f7efbd160d367d8f6b2c9f6a198b07adb9","datavalue":{"value":{"entity-type":"item","numeric-id":3936211,"id":"Q3936211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$410B4659-17DB-413D-98A5-0F5ADBABB1CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fd3a0b1f135c6dac172b52625070bb225752915","datavalue":{"value":{"entity-type":"item","numeric-id":3968972,"id":"Q3968972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$B76A3652-D210-4A84-8DF9-1B77D1FE5BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26c9fcd5f453f186f22dbf996a584a6dc92abdc2","datavalue":{"value":{"entity-type":"item","numeric-id":3663340,"id":"Q3663340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$27A58D3A-0501-4D09-B6E0-D8759B99936F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$021DA4A8-70C4-44EE-8F96-AF24E4862653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69928c586dc3eab0b629bf381f71736d6f3ad757","datavalue":{"value":{"entity-type":"item","numeric-id":3985808,"id":"Q3985808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$A050B07F-3A54-4864-B917-E6C1FC4B7DD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$2B9B05B2-7038-440D-B8E5-B3E2E81F69F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"668ede22aaf0f582cd852b85766ea7ff07a98da5","datavalue":{"value":{"entity-type":"item","numeric-id":3957959,"id":"Q3957959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$6F318E4C-EC55-4EE6-8891-2FEB7A4F6037","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":"Q1085169$AADB0B04-F8D0-4BBE-B447-EB8EE04AF15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6141476b65d14923fb002fbcd5da8a63dbb0016","datavalue":{"value":{"entity-type":"item","numeric-id":3875202,"id":"Q3875202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$ED28AD2B-07FB-45CD-83CA-92D709DA20CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$06172A07-F9B3-4D9A-90A5-3F97D9E9A64E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$078F9F82-1214-4DEC-BE7B-FCF803C94AC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcc67d47bf3c27fbeab166391b3b3e9d154ed32f","datavalue":{"value":{"entity-type":"item","numeric-id":3904539,"id":"Q3904539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085169$F5DD5089-9691-4411-82D7-E5BCD46420D1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69048f44818ec12c135495ff3fe9971a71b26d61","datavalue":{"value":{"entity-type":"item","numeric-id":4296512,"id":"Q4296512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7095a432db911ed7e9f955d44c136463d8ae014c","datavalue":{"value":{"amount":"+0.8824526071548462","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":"Q1085169$1746F2D8-6856-4B0A-A014-D4C2AD22EB50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70a728049ce9db5e14388b09062617daf5952ce5","datavalue":{"value":{"entity-type":"item","numeric-id":4873809,"id":"Q4873809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba8a01c2f4da3d09f51c9ffa6ffe2beb51d211aa","datavalue":{"value":{"amount":"+0.8765934109687805","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":"Q1085169$2C4131B4-F2EC-429A-9641-10F0F1CFC700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14048d7584e96dafd1ae8f65d95ffc620b43f096","datavalue":{"value":{"entity-type":"item","numeric-id":5232446,"id":"Q5232446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdbd226b44bb9c0fefdddd2290584fb60fbcc2ef","datavalue":{"value":{"amount":"+0.8721603751182556","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":"Q1085169$35B16CE3-37E2-463D-94BD-139CF48D65DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"510f2783241b4ddc568ae91dc4db1ea5dde04ed1","datavalue":{"value":{"entity-type":"item","numeric-id":5266605,"id":"Q5266605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fcd7dbd16948dc0811da33f787a823242a9399f","datavalue":{"value":{"amount":"+0.8717133402824402","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":"Q1085169$68C282C3-2F1A-4E54-8BDD-AFF4E79CB3FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a21ae0b51f2ff62b200a9dea42a97be76b478089","datavalue":{"value":{"entity-type":"item","numeric-id":4428085,"id":"Q4428085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42dddafbc5fe199adf8e9ebb4400ec30dc17236f","datavalue":{"value":{"amount":"+0.8628759384155273","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":"Q1085169$7EC01C68-8653-44B1-BF93-F551E74D5666","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding small simple cycle separators for 2-connected planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_small_simple_cycle_separators_for_2-connected_planar_graphs"}}}}}