{"entities":{"Q916681":{"pageid":918529,"ns":120,"title":"Item:Q916681","lastrevid":65358507,"modified":"2026-04-12T02:03:01Z","type":"item","id":"Q916681","labels":{"en":{"language":"en","value":"On two dual classes of planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4154491"}},"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":"Q916681$DCA4F31F-58AC-41A3-AE0F-1F29D1BC7D28","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"245c5987455f6117672237734ed2281b969c5079","datavalue":{"value":{"text":"On two dual classes of planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q916681$E78E84EE-A363-41AB-93C9-EF333991C804","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a5fb873b8b3820a6f6d9fcb7f8d7c2899b8db85","datavalue":{"value":"0704.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$D93A2D4A-0C39-4D9D-B71A-9F6EF0271AAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a596bfaf4af1e864ea6459b23c5c1de2646f18de","datavalue":{"value":"10.1016/0012-365X(90)90293-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$D759BE1E-F94D-452A-BF09-5896FE4533CE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"087177969742b876ace983fe9dc71a9079719999","datavalue":{"value":{"entity-type":"item","numeric-id":916680,"id":"Q916680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$C26AB7A2-F878-403D-BF72-49D9C7326C78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$E975B623-6ED7-4CA5-9599-B670FD05AE9C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$07DE6B84-ECB2-4E14-8904-49E6880B6ADF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q916681$501F4D34-04B0-4CAB-A5E7-D592D67E7A59","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6e5794ddc8146e056ec72d623b8bffaf7acd29c","datavalue":{"value":"A \\(\\Delta\\) is a cycle of 3 edges and a Y is a degree-3 vertex and its incident edges. It is shown in [\\textit{G. V. Epifanov}, Reduction of a plane graph to an edge by a star-triangle transformation, Dokl. Akad. Nauk SSSR 166, 19-22 (1966; Zbl 0149.213)] that any connected planar graph can be reduced to an edge by a sequence of Y-\\(\\Delta\\) reductions (replacing a Y by a \\(\\Delta\\)), \\(\\Delta\\)-Y reductions replacing a \\(\\Delta\\) by a Y), series reductions (homeomorphic removal of a degree-2 vertex), parallel reductions (deletion of one of a set of parallel edges), and degree-1 reductions (deletion of a degree-1 vertex and its incident edge). A \\(\\Delta\\)-Y graph is a planar graph reducible to an edge via \\(\\Delta\\)-Y, series, parallel and degree-1 reductions, with an analogous definition for a Y-\\(\\Delta\\) graph. It is shown here that a 2-connected planar graph is a \\(\\Delta\\)-Y if and only if its planar dual is a Y- \\(\\Delta\\) graph.    The \\(\\Delta\\)-Y graphs were characterized in [\\textit{T. Politof}, A characterization and efficient reliability computation of \\(\\Delta\\)-Y reducible networks, Ph. D. Thesis, University of California, Berkeley (1983)] as having no subgraph homeomorphic to \\(C_{4,4}\\) (a cube) or \\(W_{2,5}\\) (the planar dual of a pentagonal prism). Here, these graphs are characterized as having no minor isomorphic to \\(C_{4,4}\\) or \\(W_{2,5}\\) (where a minor of a graph G is a graph obtained from G by deleting some edges and contracting others to a vertex), and the Y- \\(\\Delta\\) graphs are characterized as having no minor isomorphic to \\(C_{5,5}\\) (a pentagonal prism) or \\(W_{2,4}\\) (an octahedron). The result for Y-\\(\\Delta\\) graphs specializes to planar graphs a characterization in [\\textit{S. Arnborg}, \\textit{A. Proskurowski} and \\textit{D. Corneil}, Forbidden minors characterization of partial 3-trees, Technical Report CIS-TR-86-07, Dept. of Computer and Information Science, University of Oregon; see also the same authors' paper with the same title in Discrete Math. 80, No.1, 1-19 (1990; Zbl 0701.05016)] of partial 3-trees as having no minor isomorphic to \\(C_{5,5}\\), \\(W_{2,4}\\), and 2 other, non-planar, graphs, since Y-\\(\\Delta\\) graphs are just planar partial 3-trees, and the result for \\(\\Delta\\)-Y graphs follows by duality.    In addition, linear-time algorithms are presented for recognizing these 2 classes of graphs, and for embedding \\(\\Delta\\)-Y graphs in k-trees for \\(k=1,2,3,4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q916681$D4F5C915-ADC7-4175-996B-96E340A9AAC8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$01D2BD64-DFED-438F-9AC8-857EE8F95165","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$0CED19BE-136C-4FDF-A24C-46EF56DF596D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$5BE66AB8-2454-439A-8C25-9239FF0C31FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9ca4c9f6aa08c23699aa78021b46083d69856367","datavalue":{"value":"4154491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$B213F3D2-095D-4E50-B394-5F1C630251AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q916681$BD52DFE1-1ACB-4785-BD86-5B8E61FE16F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1ecf978a28e5d1baefdbd10dbc4f102a6158a13","datavalue":{"value":"duality","type":"string"},"datatype":"string"},"type":"statement","id":"Q916681$BC6A7E13-787A-4B16-BB74-092020627E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9dbf3a8600cb49248e318e2402835658ca4527cb","datavalue":{"value":"delta wye reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q916681$E1DDB430-DC7A-4250-883D-D60CA787C8CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f46f78a5a79bcca4a45426a296a6f03962b21ac7","datavalue":{"value":"linear time recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q916681$5D599419-EB1F-4819-A362-6F3CCC9FDF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7f67c64065878c866a1eb12b275918149da7dc6","datavalue":{"value":"Forbidden minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q916681$CBA36B34-2530-4217-9422-AD3E36C87531","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$E239118F-3635-4235-A3E5-E88FDD85CE4D","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":"Q916681$9149162B-336A-4EC5-8D56-30FBBA669BC0","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":"Q916681$66A29CA3-BF60-4B4B-BF02-12D68D85BFDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0bab8d4aa9a79789c4f8631ee79af28637b14","datavalue":{"value":{"entity-type":"item","numeric-id":3266137,"id":"Q3266137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$EBC18334-B49C-4516-9180-A149A1648F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf73aba229b23f389841856465d1ea7418d3ff2b","datavalue":{"value":{"entity-type":"item","numeric-id":3042417,"id":"Q3042417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$F6916B1B-1FE9-45B9-BE61-441983A007C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98f763e865fb42b7a66d14c482658008165a710a","datavalue":{"value":{"entity-type":"item","numeric-id":3728922,"id":"Q3728922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$1A32BA31-9B94-42D1-8629-43F23B925E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2635b9d9036a6cd42517aeaa5e3c23b46c2c73a3","datavalue":{"value":{"entity-type":"item","numeric-id":913807,"id":"Q913807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$3D8C8C89-7994-4624-A31F-D6134875C2BD","rank":"normal"},{"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":"Q916681$B108024F-4E3C-46E1-A3FC-1779E5107BDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"510c108bd70aa0b73185b0377dc60493656ee460","datavalue":{"value":{"entity-type":"item","numeric-id":3026711,"id":"Q3026711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$DEBFDABF-FC13-4A64-B53D-9586EEC5E946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2807a41410595e132197f1ca423f283fef377de","datavalue":{"value":{"entity-type":"item","numeric-id":5528477,"id":"Q5528477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$BC05302C-F5AA-486D-AABA-EC2CE183F7D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$63F8709B-9892-4F4A-BEDB-E3971E75804B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$6CE22608-9E6A-4A74-AD0D-4A5DE1517C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c46e3539db645bc8c94549a117c6a14e9867d6a","datavalue":{"value":{"entity-type":"item","numeric-id":2532131,"id":"Q2532131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$166E0F06-B2ED-4E0B-953F-7A31B0FBDA79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$790146E3-1567-48BB-AC2A-D80987B696D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$0177E30A-2A5F-4B29-91F8-5BF5E05EE9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f3b8fc016d02c7cba725e987893d982bac062e7","datavalue":{"value":{"entity-type":"item","numeric-id":5334714,"id":"Q5334714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$9E6ABF03-66D1-4772-8FF9-3B713C7FEA2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bac9e96668c7ec0f829bbe6125b2c6a54e606e8","datavalue":{"value":{"entity-type":"item","numeric-id":3684139,"id":"Q3684139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$3BD8D17C-C8E1-4CC0-A129-F84086756706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71680a4ab9e1f4beb0d4c1abad68c079fb9c955","datavalue":{"value":{"entity-type":"item","numeric-id":3945592,"id":"Q3945592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$C715BB67-EAF9-485C-8C62-560FC15B302F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad9cfae9fc9d02b6b7648a5f38f2a07226c5c18d","datavalue":{"value":{"entity-type":"item","numeric-id":3311677,"id":"Q3311677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916681$05862965-B84C-4FDF-BB1B-2E449152197A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6d0a4cc7f28a70e658dc9a6a95fe78599e20271d","datavalue":{"value":"https://doi.org/10.1016/0012-365x(90)90293-q","type":"string"},"datatype":"url"},"type":"statement","id":"Q916681$2432A1F4-BFF2-4F70-B8AD-9710203C9B32","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5e4935fb5e7247f03fe35f6398c42df5dcf4df7d","datavalue":{"value":"W1997601296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916681$EAD3ECA7-D789-490F-90F8-255F39FB80B7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"990bef0f1622a5990c6000bc94203840aa06d04d","datavalue":{"value":{"entity-type":"item","numeric-id":3832586,"id":"Q3832586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ec3ed0a4d38e5e97fdd22f75b380ab33cc0e95a","datavalue":{"value":{"amount":"+0.8263348937034607","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":"Q916681$AEE4007C-13A6-4A5B-92FA-AEA0A99183CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0f8536a7fa651d6c626e1a96cde7367644141b5","datavalue":{"value":{"entity-type":"item","numeric-id":4862351,"id":"Q4862351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a999de15b3c1dd703e8e39c2b5b45e2d72d839df","datavalue":{"value":{"amount":"+0.8201742172241211","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":"Q916681$C00D6C75-A4BD-4A08-9DA0-1130F1FA43D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b011980f56d61d0252265c93ed82fe680c8adcc","datavalue":{"value":{"entity-type":"item","numeric-id":1894355,"id":"Q1894355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a999de15b3c1dd703e8e39c2b5b45e2d72d839df","datavalue":{"value":{"amount":"+0.8201742172241211","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":"Q916681$35F141C8-A4EC-4187-8905-70EB5F6B69D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f67c2ea0217f59a5ef80a13c5525197b24c283cd","datavalue":{"value":{"entity-type":"item","numeric-id":3082607,"id":"Q3082607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f72c21f6716fccb2370664b6bb5a4799efa38ecd","datavalue":{"value":{"amount":"+0.8128017783164978","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":"Q916681$5B098540-380B-4BCD-BD91-8F8F4609BAB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83c035a806595042f92896588f21e0c304d55f66","datavalue":{"value":{"entity-type":"item","numeric-id":4946544,"id":"Q4946544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf8445920e9df0b835012e0d6f4c5b712a9db19f","datavalue":{"value":{"amount":"+0.8093866109848022","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":"Q916681$1ECAEEBA-ADB6-4527-AA19-E47BB86EDB11","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On two dual classes of planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_two_dual_classes_of_planar_graphs"}}}}}