{"entities":{"Q1011765":{"pageid":1013613,"ns":120,"title":"Item:Q1011765","lastrevid":66005790,"modified":"2026-04-12T06:53:28Z","type":"item","id":"Q1011765","labels":{"en":{"language":"en","value":"On embedding a cycle in a plane graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5542414"}},"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":"Q1011765$6E1EF2C6-4B92-498D-AE6F-00EDC5ABF2B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5aa87eb724ef1838c129ca53391cced4f3be0df7","datavalue":{"value":{"text":"On embedding a cycle in a plane graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1011765$8A8AA9A3-689F-496F-893A-F9E1EE6784C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91600ca9fef512e4b87342f490f3b80213b99ddd","datavalue":{"value":"1172.05016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$7FEC2552-98B4-477D-91B0-20F057A318D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c9e4c7c2d2ffe5c9240909aa4b0ab17881b4104","datavalue":{"value":{"entity-type":"item","numeric-id":386889,"id":"Q386889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$C212FA15-42C9-4261-9050-8F2C3AF06654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"726bcdb4e73a98342cab1de1f4cfaaa421f18ee2","datavalue":{"value":{"entity-type":"item","numeric-id":386890,"id":"Q386890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$1471C149-B8F8-47E2-A1AA-B2A0F8123B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b076b2f2cf812905212b0051d13eb6b47a5745c","datavalue":{"value":{"entity-type":"item","numeric-id":202653,"id":"Q202653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$2E77AC48-8694-427A-9A7F-1DDE610AE0D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"80ce8eef3805d10cef0269e1a5235987bd5687a2","datavalue":{"value":{"entity-type":"item","numeric-id":1011764,"id":"Q1011764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$CD0AE0D7-263E-48EE-ACFF-11F7A2DC38EC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$1ADB3390-528A-4546-A570-907DD56DE410","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bcdb1993f8b4556071ee0569f4221a22eabbccd0","datavalue":{"value":{"time":"+2009-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1011765$C70A9465-5100-448F-A894-5AB5738C12FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"689dde9f9406398ada9db34207c6d7b3dcbd12a5","datavalue":{"value":"The problem of drawing a non-simple cycle as a non-intersecting closed curve into a planar graph drawn in the plane with the vertices represented as circles and the edges represented as thin stripes is considered. The problem is shown to have an interpretation in the \\textit{clustered planarity}. A \\textit{clustered graph} \\(C(G,T)\\) is a graph/tree pair with the vertices of \\(G\\) identified with the leaves of \\(T\\) and the clusters of vertices of \\(G\\) defined via shared ancestors in \\(T\\). A \\textit{drawing of a clustered graph} is then a drawing of \\(G\\) in the plane that groups the clusters so that incomparable clusters do not intersect. A clustered graph is \\textit{c-planar} if a drawing exists that does not have any (naturally defined) edge and edge-region crossings.  The complexity of the \\(c\\)-planarity testing is not known and the classes for which it has been determined are mostly the so-called \\(c\\)-connected cluster graphs. The authors study instead a class of (potentially) highly non-connected graphs called \\textit{flat}; clustered graphs of tree depth at most \\(2\\). Specifically, they consider the subclass of \\textit{rigid clustered cycles} whose underlying graphs are cycles with prescribed sets of edges to share their pipe (stripe). They introduce transformations that preserve the \\(c\\)-planarity of rigid clustered cycles and based on these transformations they present an \\(O(n^3)\\) time algorithm to test the \\(c\\)-planarity of this class (\\(n\\) being the number of vertices of the underlying cycle). They also present a method of extracting a planar embedding in the yes case of the algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$7E1AD36A-7546-4B77-9C63-E40EA4329E25","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$9276B69E-5AD5-4DF9-8276-BC6732D7A5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$59BBEF36-058F-491B-B43F-C945DD5F37FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$F3B97AD3-1C02-4FA4-8D2A-E66808A2F9EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45a54b9594829330fd795c6e7cd11863c6da4b30","datavalue":{"value":"5542414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$DF097245-2877-451D-8777-791AD0775522","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e257e9a17bc983a6f139f0c77c64fcf0b8963f7","datavalue":{"value":"graph drawing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$1BF1EE73-8349-47FE-B389-948DAE0DBD00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3b372a9f6e5635cc212214d31f4d37269dcb5f8","datavalue":{"value":"clustered planarity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$3444743E-A8C4-42E8-861F-3AEEA9689757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b9b47f43ddb2e1a0f39a4058cdba409b445ab3e","datavalue":{"value":"clustered graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$7BF50E1D-26CF-4184-B803-A73D71CCE345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3744d15beadc0dbcb2f518132d24966a53bb56b","datavalue":{"value":"planarity testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$1E6CDE19-5C01-4A63-9559-16CD1AB9A70D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$548FBBE1-CB9B-4A2B-ACEB-04141853FCB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$AA151A52-9871-4586-AB27-8AB76203F881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$630569AA-A49A-46F0-8291-4D583267AE13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1011765$B0F9B815-443D-4DAE-A337-E9BB997D10B8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"35eaf61e442e867df19139f413c267c580a3f0bb","datavalue":{"value":{"entity-type":"item","numeric-id":162920,"id":"Q162920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$C3AE72B4-6815-4C4F-A090-95D63C14AF8C","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":"Q1011765$10280865-8BB4-4F50-82B8-9F22F05D8CE9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7093af6c9fcf963e960f530401d957b816e1f0d1","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.12.090","type":"string"},"datatype":"url"},"type":"statement","id":"Q1011765$EA9F93F3-EDA9-42EE-A946-8C30ADA69467","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"075459986bd476f0cfb099944ecf07c3eca573d7","datavalue":{"value":"W4213252030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$59C97D3B-3375-48C2-A3D1-935BCB412704","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f03a5c0ef3c5fcffeeb0f59690768c9aa053660d","datavalue":{"value":{"entity-type":"item","numeric-id":4232783,"id":"Q4232783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$5C810B85-7AD9-4617-8267-C8B920AF8063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"441176e392a3704b470c00f0e63abb1f4f662457","datavalue":{"value":{"entity-type":"item","numeric-id":5902519,"id":"Q5902519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$1D4645F5-86DB-4117-8A25-1082257E40F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2a95415a07538cddde3debfb0c5cd0b03ef2a8","datavalue":{"value":{"entity-type":"item","numeric-id":5711595,"id":"Q5711595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$329C83F1-DF44-4976-9016-10C79DB1028E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e6f194b4e8870da1bd0f1095012da7718d6ea58","datavalue":{"value":{"entity-type":"item","numeric-id":3839007,"id":"Q3839007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$0EAFE0EC-8E1F-49DE-AED5-8001F2328ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d80b3e3f6867e23a4bc0cbe5e8104723369a83a4","datavalue":{"value":{"entity-type":"item","numeric-id":3043705,"id":"Q3043705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$65FF352F-7077-47A8-8E15-997AC7716345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"625a03d46620a33bee2de786dbc5e81f0c26accc","datavalue":{"value":{"entity-type":"item","numeric-id":3154375,"id":"Q3154375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$B243726B-33B2-4861-AC28-25474E499728","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":"Q1011765$A72DBBBD-E58C-4FAD-97C5-C2FAF0A0E77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"453cb6c465d0a775d82dd268754a90a38fb101f0","datavalue":{"value":{"entity-type":"item","numeric-id":6102302,"id":"Q6102302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$32D88D52-40BC-4319-88E7-D38A608FF0CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"124ed6c34f95b1f4bae87082fa2c8aa41a4ca959","datavalue":{"value":{"entity-type":"item","numeric-id":5897632,"id":"Q5897632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$93F603EF-F7A0-442D-BFAF-D1D0830664C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"365928477b66cd4015372ece1017c02bd0873f93","datavalue":{"value":{"entity-type":"item","numeric-id":4422278,"id":"Q4422278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$FD25D56A-4219-4153-8A44-67D8F2998907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44d91d72b111cce4b760bc909f1579314c09e207","datavalue":{"value":{"entity-type":"item","numeric-id":4710683,"id":"Q4710683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1011765$B09657AA-2FBA-43AB-83C6-AA34AAC6274F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"20181f30b0e3ed1db178894913c7b345d3c10664","datavalue":{"value":"10.1016/J.DISC.2007.12.090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1011765$166A7AE2-8B7B-4992-B2D2-C5B4040A9AA3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb262cb683b6e31bca6b42c7c8b79e29b6374dd9","datavalue":{"value":{"entity-type":"item","numeric-id":5897617,"id":"Q5897617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8b3286e8dca5a8e0ab7590efa4f378c99e7c18b","datavalue":{"value":{"amount":"+0.8901206851005554","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":"Q1011765$D96FBC4F-E680-4A44-8DB2-6C7FBBC4EDD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"519c76e267532754c4b1b16d0378a784fe422663","datavalue":{"value":{"entity-type":"item","numeric-id":5711595,"id":"Q5711595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99c4d3b72d57ba22f64d274f7c0d9ea94849969c","datavalue":{"value":{"amount":"+0.849010169506073","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":"Q1011765$02DA78DD-4327-4E98-9747-786542785674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad5a759ebfe8463ab4408aa6efb0778898ca8112","datavalue":{"value":{"entity-type":"item","numeric-id":3402368,"id":"Q3402368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cddf87194e371af04d4beb21df7faba26e23cf65","datavalue":{"value":{"amount":"+0.8395884037017822","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":"Q1011765$49B00111-DDF4-4963-819E-04741B520C32","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On embedding a cycle in a plane graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_embedding_a_cycle_in_a_plane_graph"}}}}}