{"entities":{"Q1346696":{"pageid":1357435,"ns":120,"title":"Item:Q1346696","lastrevid":47317276,"modified":"2026-01-01T08:31:59Z","type":"item","id":"Q1346696","labels":{"en":{"language":"en","value":"Rooted routing in the plane"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 741475"}},"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":"Q1346696$235C3397-74DE-4286-B823-263D8DF62FDD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"50804c8f3ca77d67af8f57d34060d21caa3bab49","datavalue":{"value":{"text":"Rooted routing in the plane","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1346696$85C0A088-3560-45F3-848E-922A7B23574E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a338d31689490e9277594efadd0eb87f99942633","datavalue":{"value":"0816.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$EA21089D-E616-446B-8A97-2880BC6DDA60","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"66e777069079fc2f0932237b0f85d767fc0d9d36","datavalue":{"value":"10.1016/0166-218X(94)00104-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$DC5CBE2E-A3C8-4B52-9FBB-51C36129E3E8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$0B451A4A-0DDD-450A-A2F9-788B80105013","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c22fff5067af428041487b6a008ee6b0a5e2859","datavalue":{"value":{"time":"+1995-04-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1346696$91F1BBA7-4011-4AD0-875C-AA89E2A4A860","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"73c1dfd8560f9aa81b954bcf730320de3b9eeb0e","datavalue":{"value":"A partition \\(P= \\{P_ 1,\\dots, P_ p\\}\\) of a set \\(X\\) of vertices of a graph \\(G\\) is realizable if there are vertex-disjoint trees \\(T_ 1,\\dots, T_ p\\) in \\(G\\) such that \\(P_ i\\subseteq V(T_ i)\\), for \\(1\\leq i\\leq p\\). A realization of \\(P\\) is such a set of trees. In this paper the author discusses a linear-time algorithm for instances of \\(k\\)-realizations (Input: a graph \\(G\\) and a set \\(X\\subseteq V(G)\\) with \\(| X|= k\\). Question: which partitions of \\(X\\) are realizable in \\(G\\)?) where \\(G\\) is planar. The algorithm is due to \\textit{B. A. Reed}, \\textit{N. Robertson}, \\textit{A. Schrijver} and \\textit{P. D. Seymour} [Contemp. Math. 147, 295-301 (1993; Zbl 0791.05092)]. Also considered in the present paper are extensions to higher-genus surfaces and an algorithm of Robertson and Seymour for \\(k\\)-realizations in arbitrary graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$9201FC1C-E69A-46AE-8FF7-C4B556424923","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$BAD8866D-23F7-47B4-8195-30480D8F2A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$6F68749A-5CD1-42D7-9A54-3EAE3885F0BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$DECAF001-7FC0-4672-AC88-3799738770FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$5E8BC1CE-ADDF-442B-A99F-5F9CAE8E886D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$F6171E2E-2030-471B-9E1A-900DED0229F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$DC245D7D-DF92-4AFD-8FDC-8DE219CD8578","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dbe09518ee54dffcf2e3363696a6d5651f1dc12c","datavalue":{"value":"741475","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$B69AF5AD-625A-476E-AB6D-72937034B539","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9b44686801c10009bd80a372e4956abfdc4cc6b","datavalue":{"value":"rooted routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$6A8B0099-BE7A-4448-8122-07DD32EE141C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93cbb2598457bc7d69b5a536074cc48914824680","datavalue":{"value":"plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$21CFC333-3BC7-42D3-8DA7-000E532A2DC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$D6CDAFFE-B901-4A96-A414-F73FEDD13117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$F503123A-B3B4-4640-8E57-6995DAB6B919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b355c8a4174d6d8394d7bf240c24bc9a0be14b8","datavalue":{"value":"realization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$3ADC2439-B86D-4E03-B4F6-292F3389067A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$2C93E119-6E68-4067-8B50-B855546E992A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f70a8dba8f1e67b46010856a9c258ae3a85adf5c","datavalue":{"value":"higher-genus surfaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346696$A48999B6-5E3D-4F5A-8D33-747B1D18AEA4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$7063D9DD-6D2E-4922-B1B0-5B8E497CA38C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$C5676542-01BD-44B4-BEC4-94ADE2C6D509","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":"Q1346696$9B03D589-B87D-419E-B523-690206C1591E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$B6EFDDB7-EBCA-472F-9E0A-90C8782B9515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ae06ace3264ebdef666fd198a2d1441400a748e","datavalue":{"value":{"entity-type":"item","numeric-id":4087195,"id":"Q4087195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$BCEFBF8F-93C2-4094-8A41-6CD635F74CAE","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":"Q1346696$ACC4D672-3F2F-41A4-A1A2-2C38550BF607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$58B59B9C-D45B-4150-B996-2D6F4BCA44C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9cd5ab2b4dcc204e3d6bd923419ed31e399a96a","datavalue":{"value":{"entity-type":"item","numeric-id":1079580,"id":"Q1079580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$08B1C941-8139-4AFE-9051-0253D7971A05","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":"Q1346696$6D7C061D-4F8E-419A-9D84-BC002BD4ABF8","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":"Q1346696$CD642909-6131-47EA-8403-212F1694BC79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d835ccc7da104c96eb1a22d7d8e47a280dbf09","datavalue":{"value":{"entity-type":"item","numeric-id":1150632,"id":"Q1150632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$B3ECD0B8-B588-47B5-B33D-C98D84996039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32cfb1bd9a2e4985fe859e378e81598a196911d8","datavalue":{"value":{"entity-type":"item","numeric-id":3930654,"id":"Q3930654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$390C1F62-17A1-48B2-A770-6914DFDF7447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57e71e5b556401efd16915950de24e05b8ad7db1","datavalue":{"value":{"entity-type":"item","numeric-id":4156452,"id":"Q4156452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346696$FDA5E8BC-BA07-4239-839F-0F7F40548DB8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"22adb6e682bd91eec876b0e28ba794de48b90654","datavalue":{"value":"https://doi.org/10.1016/0166-218x(94)00104-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q1346696$89AEF032-23F5-4361-BE10-2A41E70AF085","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0aaf578f369d23d711029a0945ca1077f616008c","datavalue":{"value":"W1984897155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346696$85EA7917-4989-41FD-B216-52C4370FB1F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34cb3f751b43545520d86f963af701377a81280e","datavalue":{"value":{"entity-type":"item","numeric-id":4280136,"id":"Q4280136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74f4e27b034612b31c642ae206e65234bf0a48cf","datavalue":{"value":{"amount":"+0.90446799993515","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":"Q1346696$F465000B-6D9D-43B0-B65D-886244D1F2D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"127006cddd28add3bfb10592741f8379d5f470d9","datavalue":{"value":{"entity-type":"item","numeric-id":1179127,"id":"Q1179127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5487e9c26f64d2469023c59826df7e5e96b79ccd","datavalue":{"value":{"amount":"+0.9030708074569702","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":"Q1346696$601D4EC0-DFE2-4559-A000-D207AB28E661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89ef006d03922a13481438cec1f9a6ad7d5f7f09","datavalue":{"value":{"entity-type":"item","numeric-id":3832583,"id":"Q3832583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1198c1cac37325b221810937fc96f962fecfc38","datavalue":{"value":{"amount":"+0.7909297943115234","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":"Q1346696$C267D551-0BC5-421B-B481-BDFFFD68D169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d58c2d1d7817f8c6d53256e825ccf8cabd046918","datavalue":{"value":{"entity-type":"item","numeric-id":3595491,"id":"Q3595491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3c953a60629a79006fccd7987d13d54c3ea089f","datavalue":{"value":{"amount":"+0.7704706192016602","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":"Q1346696$766D644B-A77E-482F-B8F7-17C147CDE1F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8af42e805cbe81a9f339b982bee6c3c97caf912d","datavalue":{"value":{"entity-type":"item","numeric-id":4232799,"id":"Q4232799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ac6529624c12438a17b482bbb6bc87e2e4db41b","datavalue":{"value":{"amount":"+0.7635221481323242","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":"Q1346696$73677CED-B68F-456C-9DF1-36764DE707F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1346696","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1346696"}}}}}