{"entities":{"Q1382263":{"pageid":1393003,"ns":120,"title":"Item:Q1382263","lastrevid":67304580,"modified":"2026-04-12T16:43:34Z","type":"item","id":"Q1382263","labels":{"en":{"language":"en","value":"Edge-packing planar graphs by cyclic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1133159"}},"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":"Q1382263$C01BAD08-50BF-4A2E-A5FC-D160F57BA657","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a4c2d3f3a0ab09b1050b1d3be6db2a6bb0ea5c1c","datavalue":{"value":{"text":"Edge-packing planar graphs by cyclic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382263$E61431DB-E1FA-4109-AD97-8823F4A27705","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa9928d6bf92e0e4cc9b9ca7fc912bd69a0d25b8","datavalue":{"value":"0899.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382263$B04EB5E7-0967-439B-8289-3FAEC6EBF898","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f04b2954a8a75ca070184b5dcf9683f74febba45","datavalue":{"value":"10.1016/S0166-218X(97)00083-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382263$1CEA792E-49FA-4FEB-BDFD-424DF6F34197","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa314e25f5bb4048205d001e92d556b2eff4c119","datavalue":{"value":{"entity-type":"item","numeric-id":176420,"id":"Q176420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$A3A4CD59-5234-4BBD-80CE-3EE995DDCA8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"66bd5b72e2245f11b8fbe5c04b255234dbdaf937","datavalue":{"value":{"entity-type":"item","numeric-id":1382261,"id":"Q1382261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$A516027D-2F36-44AA-B3C9-2AE26C93A59F","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":"Q1382263$18B9EA30-7A4B-4B38-9D21-E7CB32CFC21E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5399645c428137aebf8ec27d073066145a6d5c40","datavalue":{"value":{"time":"+1998-03-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382263$D4BE267B-274A-4FCA-84C4-4C38835150C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1382263$DB3EAB30-F00C-4421-8D67-A634C2020C87","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e0b369226a22ebaa03a5e16eed96cdaf76ba9f4a","datavalue":{"value":"Let \\(G\\) and \\(H\\) be graphs. An edge-packing of \\(G\\) into \\(H\\) is a collection of edge-disjoint subgraphs of \\(H\\) each isomorphic to \\(G\\). A maximum edge-packing is an edge-packing with the largest number of subgraphs. In this paper, the case when \\(G\\) has at least one cycle and \\(H\\) is planar is considered. Under a wide range of conditions on \\(G\\), determining whether a packing with at least \\(k\\) subgraphs is shown to be NP-complete. In the process, some difficulties with the proof in \\textit{D. G. Corneil}, \\textit{S. Masuyama} and \\textit{S. L. Hakimi} [Edge-disjoint packages of graphs, Discrete Appl. Math. 50, No. 2, 135-148 (1994; Zbl 0793.68114)] are identified.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382263$6DC3CA3A-2C82-4B76-9452-D958A7B0CCE9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382263$0CF5593D-FD0C-4433-A390-F5CC420F0982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382263$EFBAEAFB-99A0-4188-8EA5-BC102BB41EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382263$792A2C1A-7FEA-4000-875A-F72EF327C18D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7f0f20235040356934c34731c634225c2dc4090b","datavalue":{"value":"1133159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382263$8C8196A5-A31E-438D-AFCC-9FCF8F180BA9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382263$FAA24D0E-93EC-45E6-8498-B576F2DC5C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b229bfcfa90bc5d6ffbe62dc60a27292803fe8b4","datavalue":{"value":"edge-packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382263$BEDE2367-EB4C-443A-8524-FB08064086CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382263$53EA958A-31EB-4111-B6E7-6D70360B6EA8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8ba0869bc4942831c8669ed75022f72a56f93072","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$9A46316C-5984-4E23-B3D9-38959F742DE5","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":"Q1382263$A10AF6F3-8FC9-4E22-81CC-27002202C57B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$D9BDC15D-AA04-48F5-88D1-B006767E1654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d0665e7edb5f88a2240e9018e97da14e70e2365","datavalue":{"value":{"entity-type":"item","numeric-id":1326750,"id":"Q1326750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$472A7883-AD98-46F7-A6BD-A565BE8DE598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9acb0c4ba95f9593d97cdc8287b5522597bc52cf","datavalue":{"value":{"entity-type":"item","numeric-id":1272595,"id":"Q1272595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$31A38F74-8210-461B-8AC1-0C352551DCE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$EC48E3CF-4A1D-4CDB-81DF-2E9C5A973143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$B51C418E-C29F-4574-9695-01C0D4B82238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda4db6932bc09b3f06443166269517c1ff8ac7e","datavalue":{"value":{"entity-type":"item","numeric-id":2645931,"id":"Q2645931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382263$5F90F873-4477-4240-ACB3-0827D6DD7808","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":"9f3c9b4c19976251dfce33612cf3cd0c4a91c908","datavalue":{"value":{"amount":"+0.8705552816390991","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":"Q1382263$16524432-E2A5-407E-B2B5-5BF51EF4AED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc5f0d21ae387428bd9fb028d6058a113e7f5166","datavalue":{"value":{"entity-type":"item","numeric-id":1326750,"id":"Q1326750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a75c992d44e2d473d5c95f210aea6f4ecd84a811","datavalue":{"value":{"amount":"+0.8329008221626282","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":"Q1382263$08D08F74-259A-4A2F-B4FD-05E2CCEA3C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea5c806f8026fc23e8543b943fb753d034b44a19","datavalue":{"value":{"entity-type":"item","numeric-id":3404145,"id":"Q3404145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd43b0370433379e8a3df42446c6d6d76482ad1c","datavalue":{"value":{"amount":"+0.8099628686904907","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":"Q1382263$877A2535-71FF-421D-9FC5-B854DE679AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"375e748f2d24c9e41e14eb712708c10597f753cf","datavalue":{"value":{"entity-type":"item","numeric-id":2816101,"id":"Q2816101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92b73c30418bd23d210e29decc9a7bd02708bc32","datavalue":{"value":{"amount":"+0.7994915246963501","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":"Q1382263$7D4010A5-1B21-4305-A343-51F18272201C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edge-packing planar graphs by cyclic graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Edge-packing_planar_graphs_by_cyclic_graphs"}}}}}