{"entities":{"Q1962022":{"pageid":1972764,"ns":120,"title":"Item:Q1962022","lastrevid":47437177,"modified":"2026-01-01T18:17:02Z","type":"item","id":"Q1962022","labels":{"en":{"language":"en","value":"Maximum packing for biconnected outerplanar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1394992"}},"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":"Q1962022$2732310E-3DDE-4E50-A5B4-6F209117E2C8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a9820a8eb8455ad197d0036f292728dd66b29764","datavalue":{"value":{"text":"Maximum packing for biconnected outerplanar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962022$FAB655D3-E45D-4C05-8EFC-77CEF3C5C007","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"637cfba8b2604add24be321ec85db847c6146e7a","datavalue":{"value":"0944.05075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$4774865B-B0DB-47DA-A0DE-40B79F9E33D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6d49224510d2a90890c97425e80ae4df0b4895b","datavalue":{"value":"10.1016/S0166-218X(99)00176-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$0BF03858-E263-4221-88F4-A04901AAF084","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc5c6e9b88c2b9718796544d65ea8cbf958f5725","datavalue":{"value":{"entity-type":"item","numeric-id":1962021,"id":"Q1962021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$412FD4C4-EA90-44E0-B2A8-47BAA1ADCCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00dfebb11dde3a8ec3e20741cb39008a3351335c","datavalue":{"value":{"entity-type":"item","numeric-id":293198,"id":"Q293198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$227B45C6-F1E2-4C0F-A373-E6FBC2A08416","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":"Q1962022$CD533DC1-7BC2-4094-AE5B-C163D2C0C0F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8419f06ab8e0f2e62a9db4d1f2de9ef32bd29c48","datavalue":{"value":{"time":"+2000-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962022$A52C9ED7-E9D6-402A-970D-7455E18713C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9be10c0215b976f77de76a586ceba327485d0761","datavalue":{"value":"A \\(G\\)-packing of a graph \\(H\\) is a set of vertex-disjoint subgraphs \\(H_{1}, H_{2}, \\ldots ,H_{l}\\) of \\(H\\) such that each \\(H_{i}\\) is isomorphic to \\(G\\). The problem of maximum \\(G\\)-packing in \\(H\\) is to determine the maximum cardinality of a \\(G\\)-packing of \\(H\\). In general, the problem is NP-complete, even when \\(H\\) is a planar graph, and is generally, as hard as the subgraph isomorphism problem. Recently, for trees an \\(O(n^{5/2})\\) algorithm has been reported.    In this paper, the authors present an \\(O((n_{g}n_{h})^{2})\\) algorithm for the problem, when \\(H\\) and \\(G\\) are biconnected outerplanar graphs, and \\(n_{g}= |V(G)|\\) and \\(n_{h} =\\;|V(H)|\\). The method involves meticulous calculations of embeddings of partially triangulated polygons of \\(G\\) into such polygons of \\(H\\). Extensions of the problem to topological \\(G\\)-packing and homeomorphic \\(G\\)-packing are also discussed. The result has potential applications to image processing, chemical structure analysis, and computational biology.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962022$167D73A3-F79E-4A68-A55D-8ADACF70E1C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$39DF428C-9EC3-4CBE-8302-FEED8A364986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$9F336153-2C63-471B-9196-378443EC704B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$4199908A-8AF5-4341-A962-A2049AD7852F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d41cc602979822ad779c4260f668e3f42d8bfb1","datavalue":{"value":"1394992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$9713E91D-EEC2-4B1A-AFC0-DA4B6E270D8E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdb2f76e99657fbd2c8bfe8ee7a024355938aa9d","datavalue":{"value":"maximum packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962022$321A26DD-CD11-4722-A277-2DBA37764FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce7e478882c4aa649376efe9819470c1c50e3881","datavalue":{"value":"biconnected outerplanar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962022$7F475A99-C6E4-4115-8680-ED8B5BE6B427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2155b1f0f1b7934ea2f00e74be522bfbe52774","datavalue":{"value":"directed acyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962022$CFF0D06F-3663-4EED-80FA-65AD4BF09B48","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":"Q1962022$D53A54DF-2553-4F79-8DA9-CF316A4740B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b82c3e39edf2dcf3264ac4e0f9a3d304396deef","datavalue":{"value":{"entity-type":"item","numeric-id":5941062,"id":"Q5941062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$0BDC3478-8C1B-4542-AFC0-9A29292350AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$59668E62-BF6B-443D-98E4-AC0C3FEB3615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$26F8665B-409F-4930-93EB-FC6F83569C28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a0e7b1bee31f36c5de9b30b0020f2d8de7d56e","datavalue":{"value":{"entity-type":"item","numeric-id":3357535,"id":"Q3357535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$BC68F78E-D9A0-42EE-8918-AE86E1F1F726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ba062e35f5b9f4b7072a7b25dd2ea1a17ea1d6","datavalue":{"value":{"entity-type":"item","numeric-id":3795218,"id":"Q3795218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$C2240F82-46E7-457D-B6EE-09D25282360A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$4D405D12-2B75-44AE-B87E-EC49D8224B26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fefcce4b37048902d68e52aa98516fea4985eb16","datavalue":{"value":{"entity-type":"item","numeric-id":4595511,"id":"Q4595511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$3EDB381F-BB8E-428B-ABE2-6DA022FB1179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11b69c913da206f824441f766b25557c0bf66f60","datavalue":{"value":{"entity-type":"item","numeric-id":4593952,"id":"Q4593952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$E1DCF724-8FB0-4172-9D70-D6234B20294B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a259690ae283b3d41549f2793a233a2898cf4590","datavalue":{"value":{"entity-type":"item","numeric-id":1149783,"id":"Q1149783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$DF05B7E1-9E50-48C7-A466-C7E54E8D4FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b14233efbc23e31889365df721ca3ba294a25b","datavalue":{"value":{"entity-type":"item","numeric-id":5402563,"id":"Q5402563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$F660A744-C6EB-41D7-A508-3E735F8D64E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b1f8dacc5aa90cea438e987291a95980f58b616","datavalue":{"value":{"entity-type":"item","numeric-id":1823708,"id":"Q1823708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$4C87A2B7-35C8-4FC4-B1EF-9A544F791DCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a55798830b8903453c72e4745efc13f8aa9c4fb","datavalue":{"value":{"entity-type":"item","numeric-id":1391314,"id":"Q1391314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$4C202945-ACFD-484D-B227-61DE1B5BDA67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d030893a2c84a0831f4de47eb6811d2976e0da","datavalue":{"value":{"entity-type":"item","numeric-id":1262768,"id":"Q1262768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$54369F59-4485-4BD1-A528-02B549B5A193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b03d8bef8b97a5894ef25c8ee47fd7b1a813bb","datavalue":{"value":{"entity-type":"item","numeric-id":3804190,"id":"Q3804190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$4AAD8F4C-4D5C-41EE-8D1E-DA7C65C3FC55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd4d510824fc8b38e1a4216d17aa3840f4920281","datavalue":{"value":{"entity-type":"item","numeric-id":1201267,"id":"Q1201267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$E75D11AD-5B16-417A-9746-E4FD0955BBC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f41d5e8d3c003ac9188dc5fb1f2879b5e9b1ecb","datavalue":{"value":{"entity-type":"item","numeric-id":4172071,"id":"Q4172071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$C9F84455-8FD9-4167-A3A4-A1C795193E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5391b5cfab07d4f16078cf27797637671198636","datavalue":{"value":{"entity-type":"item","numeric-id":1144938,"id":"Q1144938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$E6FF1A36-28B0-4FA4-8D39-BCFBF3D8EEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$30B072FF-7C8D-4551-99A0-4A033E805F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b50bad9b5e66b2da9e23a06d8d2e993a52d5f6b","datavalue":{"value":{"entity-type":"item","numeric-id":1056237,"id":"Q1056237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962022$144FB756-B9F5-47D1-A00D-35CC37D73E90","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"53d1b22d41a9c664d7e2a890f7b892b2cda871f7","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00176-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1962022$D2D396C1-274D-4B65-8732-4A743A19986B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa8fc6c0c07942b93ec90e0b6253d5627d5b9b56","datavalue":{"value":"W2105366839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962022$1406663A-CCD7-4BD1-86C5-DB72D1F6723F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0550e0856e710744b4c6315ce893d9dad9239d8","datavalue":{"value":{"entity-type":"item","numeric-id":1272595,"id":"Q1272595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88acf6be7ea1480823afee7eef11b95274f278b8","datavalue":{"value":{"amount":"+0.8267064690589905","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":"Q1962022$895F503D-A2B4-40A4-839E-90D525D6D3D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ff8f01cf842997e2edf16b45f5e01e977e52c04","datavalue":{"value":{"entity-type":"item","numeric-id":1978642,"id":"Q1978642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d63eb67b79af19cb05813e5adfd0d5af7481c715","datavalue":{"value":{"amount":"+0.7936855554580688","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":"Q1962022$C86744C1-A790-47BD-988C-397BD25D446F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"439ee7d07c1da4ba425c95d112407d3f5a76257d","datavalue":{"value":{"entity-type":"item","numeric-id":1391314,"id":"Q1391314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fac12bc1c5d6921b81452b1ed8ef6df63aa4759","datavalue":{"value":{"amount":"+0.7887563109397888","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":"Q1962022$4CE1D1BE-5C31-4688-A1F7-9910F434FEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ada5cd171d31366e6d3a88d85a75405f17e4621a","datavalue":{"value":{"entity-type":"item","numeric-id":3731030,"id":"Q3731030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"672e624d63f9a127ca916d34033aabf6994eedc0","datavalue":{"value":{"amount":"+0.7880291938781738","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":"Q1962022$BB874ED4-EAE4-43E7-81A5-B4642E754E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"072bd1b3b66e9567984bfe0be1fc6241b336bc16","datavalue":{"value":{"entity-type":"item","numeric-id":1382263,"id":"Q1382263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41a1a6b0799857c3bf0eae26b79e71db77ac1932","datavalue":{"value":{"amount":"+0.784868597984314","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":"Q1962022$E72C2BB3-F048-40E9-8CF2-53D02B0CABED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962022","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962022"}}}}}