{"entities":{"Q1410408":{"pageid":1421148,"ns":120,"title":"Item:Q1410408","lastrevid":68640000,"modified":"2026-04-13T01:07:08Z","type":"item","id":"Q1410408","labels":{"en":{"language":"en","value":"Convex embeddings and bisections of 3-connected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1992713"}},"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":"Q1410408$D3F7A1A4-F080-4782-92AD-C379847D88EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a5e618ab25744d65cad15924072f5ffeacf6e81","datavalue":{"value":{"text":"Convex embeddings and bisections of 3-connected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1410408$2A59BA7A-41B7-40F0-B595-5ADE6C37542E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d9ad693ece0cc6c4558e0dfe58f6fcb7214d0e4","datavalue":{"value":"1026.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1410408$D9D7A47B-83C7-4EA0-AB3D-0AE4DCF8C832","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60eb2392c3cbb67419a7505eb4d7770437782b61","datavalue":{"value":{"entity-type":"item","numeric-id":187130,"id":"Q187130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1410408$2B5E0FD9-2F15-4BF9-B0DF-CB7E9355D78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"720a2470955600a0e199ea4312c70a5e6b991176","datavalue":{"value":{"entity-type":"item","numeric-id":226798,"id":"Q226798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1410408$B13E1E02-7BD0-4953-8D68-1028481B4064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23c4988599b52ac33fa6f0dffc34127dd48cd166","datavalue":{"value":{"entity-type":"item","numeric-id":1410407,"id":"Q1410407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1410408$1BA98D6C-28A1-4887-A239-314AB1FF897A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"746535ddb96ae77c4a55cf2874e59b3bf4f00d57","datavalue":{"value":{"entity-type":"item","numeric-id":171928,"id":"Q171928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1410408$048214F5-0B73-42DF-9477-FF826C9BA748","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":"Q1410408$48C110FA-D765-46E6-9541-5E669CC9D105","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f53eb7c5b8d889f1baf94cbfff14c8443ad94909","datavalue":{"value":{"time":"+2003-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1410408$53ED6A1C-AB6C-4AA7-8C61-7858AE65425A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a26c9aa59da71bad8e0a1d5bade7ef4c6695cdca","datavalue":{"value":"The authors prove the following result. Given a 3-connected graph \\(G\\) and two disjoints sets of vertices \\(T_1\\) and \\(T_2\\) of even size, it is possible to partion the vertex set of \\(G\\) into sets \\(V_1\\) and \\(V_2\\) such that: (1) the subgraphs induced by \\(V_i\\) (for \\(i=1,2)\\) are connected, and (2) \\(|V_1 \\cap T_i|=|V_2 \\cap T_i|\\) (for \\(i=1,2)\\). In fact, such a partition can be found in \\(O(|V|^2 \\log |V|)\\) time. The proof is carried out in two steps; first it is proven that \\(G\\) has a convex embedding, then the well-known ham-sandwich theorem gives an appropriate cut. The later one can be done effectively, see \\textit{H. Edelsbrunner} and \\textit{R. Waupotitsch} [J. Symb. Comput. 2, 171-178 (1986; Zbl 0623.68058)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1410408$7F252E08-BB99-49FA-8D44-EDC7C0492F08","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1410408$D6FFA914-F984-46A7-983D-2F6647C237DC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1410408$CB2085D2-0EBC-40BA-A07B-F97D9068DDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1410408$3C756319-8E82-40A2-A6E1-60960C4E7BAF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"88ae8019645a300be3b42375c337cfda47af43b2","datavalue":{"value":"1992713","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1410408$AB3127AF-B6DC-41C4-AA63-A83E031ABFBC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37e560e2bce251e251dc85c629febf5fdf8f4a04","datavalue":{"value":"convex embeddings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1410408$B3A434E3-71E5-41FD-8F14-86BC45E2101B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1410408$E1A480BF-F144-4084-B6B3-C829C21A3F05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57a81c28d2d76b72124671804c2a6fa1c1743797","datavalue":{"value":"ham-sandwich cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1410408$34FC6AD6-9B88-45F9-A996-6230F123B3F4","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":"Q1410408$61718900-C64B-4B52-A629-B057CBE3C1A2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"001115bfab7d4b423d3a03adf64880b6e1f2b69f","datavalue":{"value":"https://doi.org/10.1007/s00493-002-0006-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1410408$4AAABA1C-BA9C-43EA-9915-4728E11A20E5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c5f97d7e114b224da8a987776149ce09af2bfbd6","datavalue":{"value":"W2060623579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1410408$9AFCD173-E65C-4E71-BC14-520A6F62D3C3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f463cc0d0f056ad835d0a420b1cc90aae75b9d05","datavalue":{"value":"10.1007/S00493-002-0006-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1410408$EAA32A7E-4769-492F-BA2B-81CDA6BE0DD6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3003557da651899eb46ecdb25ac13586b34be260","datavalue":{"value":{"entity-type":"item","numeric-id":4511243,"id":"Q4511243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b45ec53c7e9305afa0fe63dff1b0ed5831eadc75","datavalue":{"value":{"amount":"+0.923975706100464","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":"Q1410408$AF72FCE9-9680-4E78-BF07-38C20F933ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3f9f5e545167a792d25a0bc82a51c3fb4c29c4a","datavalue":{"value":{"entity-type":"item","numeric-id":1178190,"id":"Q1178190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"880574f64c54fd795f7d76c5ab832253fd6914cc","datavalue":{"value":{"amount":"+0.9228360652923584","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":"Q1410408$502C1089-84F7-44E9-9782-72B7047B1A3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"781781b9fd098ec4ffa7c2fc4e58763880c38d13","datavalue":{"value":{"entity-type":"item","numeric-id":2566018,"id":"Q2566018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db58fd5de5886579dd50d9ca84b3d8725c9fc4b8","datavalue":{"value":{"amount":"+0.8328290581703186","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":"Q1410408$C4ABD841-2CAC-4D16-B425-EE0D301DCEC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c47a8a4b038dc37a59ee2544b2977f9d0040e8a","datavalue":{"value":{"entity-type":"item","numeric-id":997070,"id":"Q997070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ce0f86a379b836001d6d4346ee56b70076b6acb","datavalue":{"value":{"amount":"+0.8207096457481384","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":"Q1410408$BCF30275-A77B-4B9C-BCEE-20A9DBB8F930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9ec87dfa6f4edcbf7bc185eef940b699be289ef","datavalue":{"value":{"entity-type":"item","numeric-id":5897851,"id":"Q5897851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05f887b6310279bfe10b2127ce9d15ae8c66ec21","datavalue":{"value":{"amount":"+0.7877344489097595","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":"Q1410408$5F54C7C5-A88F-42BC-9CC2-61DF8626BB21","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Convex embeddings and bisections of 3-connected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Convex_embeddings_and_bisections_of_3-connected_graphs"}}}}}