{"entities":{"Q4511243":{"pageid":6540836,"ns":120,"title":"Item:Q4511243","lastrevid":108652328,"modified":"2026-11-09T15:32:23Z","type":"item","id":"Q4511243","labels":{"en":{"language":"en","value":"Bisecting two subsets in 3-connected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1522947"}},"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":"Q4511243$A74FA258-932F-4ED9-8D2A-AC4396904529","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9028714919bb3431a56fdce5ed864c5278f59efd","datavalue":{"value":"0973.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$DB2ED38A-846B-48AC-9BC5-11782E7D182F","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":"Q4511243$FAFB0CFF-9918-431F-BEA3-8FF4153FA0AB","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":"Q4511243$FFC976F2-1082-4454-B6EA-5F67352063D5","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":"Q4511243$571769BD-1FD9-44F9-81C3-901E38A2C921","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":"Q4511243$2B9CE1D0-F825-4AA9-B4DD-606EF4D94F49","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c5332c48de08b7b8da8f565721b384b6d4a11a4","datavalue":{"value":{"time":"+2001-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4511243$EA339509-FE21-45CB-8831-198C09694B0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$A9093F54-141F-4383-B3BA-65519F349685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$00F72D5D-CBBD-42AB-950C-12DAA38E5031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$687654E2-C63D-43AF-975F-79103A8E633E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$CB7870A8-E128-4879-8275-CB3A00309447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$AD107E8F-DE92-43B6-97CD-CC69443A2902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$2618501A-E73B-44CA-A6BE-783DEB6D8A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$01F460C8-C15C-40FE-8882-4B1E848B2AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$F37AD59A-6AD3-4112-93D9-F6B79F74C3B1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"407f74ed21750d44625350688eaf4613371fa6aa","datavalue":{"value":"1522947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$21665590-DA78-47E8-92ED-920634C73633","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57a81c28d2d76b72124671804c2a6fa1c1743797","datavalue":{"value":"ham-sandwich cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511243$9F1AFF8B-DC7E-4788-B59F-5F21CF07C7F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5e0748da353cbaca68136c5462da6bce39666c","datavalue":{"value":"3-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511243$DC1062C1-676C-4A42-809D-12DF003CB04D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61f168965e31defe93185084bddb5a1681ce59f8","datavalue":{"value":"bisection","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511243$1CCF463A-A93F-498B-8D75-BD52428DF7EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3afba1c885452e3a5e1e536a21d5c657eb8355a","datavalue":{"value":"graph-partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511243$011D4494-3177-437A-9F80-B57EA271DFED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f7c1c26e18666d296c6d019e84649979784d6f2","datavalue":{"value":"convex embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511243$0B2C9CCB-DE51-4435-9816-5C17481E7007","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":"Q4511243$CC45D21D-11DA-46C6-95C7-326E41620C8D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c7318b7310cfae85574c691714ed1bc6cf432b","datavalue":{"value":{"entity-type":"item","numeric-id":1410408,"id":"Q1410408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1b580037b027c7fe29cef57cdc0d0bcb070e639","datavalue":{"value":{"amount":"+0.9238105416297911","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":"Q4511243$B6282E5B-CE76-4A3D-AD9C-6401AA9546A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60430acb9eea0ab0a4b1ed373f8842b548f24920","datavalue":{"value":{"entity-type":"item","numeric-id":1730254,"id":"Q1730254"},"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":"Q4511243$C55D1D1F-96E0-44EE-B4C5-F2D44BE2915F","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":"464aebec7ec345786cf13b49bbda2e3f15c15108","datavalue":{"value":{"amount":"+0.8595184087753296","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":"Q4511243$4D66E464-BBB6-4A60-AAE8-22200D22EB89","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":"0f493dfc1f37611bde3ab305ee6bb0e3f007cbf5","datavalue":{"value":{"amount":"+0.8251458406448364","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":"Q4511243$AE60775F-778A-4096-9DB4-4F37C6DC0727","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":"e5cf386b629292b388c0b5875da661c3d2575de6","datavalue":{"value":{"amount":"+0.8066262006759644","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":"Q4511243$75611820-247B-4A86-9062-3955C3CA9276","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df01d9c5ea033452188e9f958b5aa4ed61ce6e10","datavalue":{"value":{"text":"Bisecting two subsets in 3-connected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4511243$B401FF5F-581F-4A62-8B5F-968A721F3895","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1a759580ba6f18ed380e7f5ffa7afa27da52a634","datavalue":{"value":"10.1007/3-540-46632-0_43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511243$B1B437F7-23A3-4848-A972-21E986E81167","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3bf876f18f6d6952dd0e1b6afe5359d883e30c2a","datavalue":{"value":"The \\(k\\)-bisection problem is defined as follows: Given a graph \\(G = (V,E)\\) and sets \\(T_1, T_2, \\dots, T_k\\) included in \\(V\\) with \\(|T_1|, |T_2|, \\dots, |T_k|\\) even numbers. Find a bipartition of \\(V\\) into two sets \\(V_1, V_2\\) such that the graph \\(G[V_i]\\) induced by each \\(V_i\\) is connected and \\(|V_1 \\cap T_j|= |V_2 \\cap T_j|\\) \\((= |T_j|/2)\\) holds for \\(j = 1, \\dots, k\\). The authors consider the \\(2\\)-bisection problem and show that for each \\(3\\)-connected graph a \\(2\\)-bisection exists and can be constructed by a \\(O(n^2)\\) algorithm. For proving this result it is shown that every \\(3\\)-connected graph \\(G\\) has a strictly convex embedding, i.e., it can be embedded in the plane such that the convex hull of the vertices corresponds to a cycle \\(C\\) of \\(G\\) and that each vertex in \\(V \\setminus V(C)\\) is in the convex hull of its neighbors. This implies that each straight line in the plane separates \\(G\\) into two connected subgraphs. Thus, using the linear time `ham-sandwich cut' algorithm by \\textit{C.-Y. Lo, J. Matou\u0161ek} and \\textit{W. Steiger} [Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, No. 4, 433-452 (1994; Zbl 0806.68061)], \\(T_1\\) and \\(T_2\\) can be bisected simultaneously. It is shown that an strictly convex embedding for a \\(3\\)-connected graph can be found in \\(O(n^2)\\). Furthermore it is stated without proof that deciding whether an arbitrary graph has an strictly convex embedding is NP-hard. For the more general case of the \\(k\\)-bisection problem, the following conjecture is given. If \\(G\\) is a \\((k+1)\\)-connected graph and \\(T_1, T_2, \\dots, T_k\\) are pairwise disjoint vertex sets of \\(G\\), each with an even number of vertices, then \\(G\\) has a \\(k\\)-bisection. For the entire collection see [Zbl 0933.00045].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511243$2C972456-1710-435C-885D-2AE84E554511","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4511243$3E094195-89FC-429B-B421-E5A63AC66080","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bisecting two subsets in 3-connected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bisecting_two_subsets_in_3-connected_graphs"}}}}}