{"entities":{"Q426901":{"pageid":428668,"ns":120,"title":"Item:Q426901","lastrevid":61796937,"modified":"2026-04-11T01:43:05Z","type":"item","id":"Q426901","labels":{"en":{"language":"en","value":"Improved upper bounds for planarization and series-parallelization of degree-bounded graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6045718"}},"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":"Q426901$9B6DDB8B-B731-4909-8136-E3D44ADF9110","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"822bf5a612679015add59122da2e8e6743a86d68","datavalue":{"value":{"text":"Improved upper bounds for planarization and series-parallelization of degree-bounded graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q426901$C7EDD4E0-88DA-49AF-89C2-8F97B70F9145","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a1b2fdcd62f657b1a72d3921d98403fb15c08bdd","datavalue":{"value":"1243.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$997D2E1C-A06D-45D6-A7B2-07186159F834","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6e1f9ad498b53f98afc6a2f82e96c5f4554c2c2","datavalue":{"value":{"entity-type":"item","numeric-id":383737,"id":"Q383737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426901$670E129C-FB67-44B7-96FE-5FADD5B47120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c10b05f408b175fc9b864bccc0f940febdbc4691","datavalue":{"value":{"entity-type":"item","numeric-id":810039,"id":"Q810039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426901$3D0CA00F-C0CE-4182-813A-E93EBEBF66C1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426901$B1EFA1E0-6319-4E78-A7D4-D522C82EF76D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4bc8e8f32e3771ea3dc331f4cf4795267b160813","datavalue":{"value":{"time":"+2012-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q426901$9C688114-5396-4F77-A1D7-BB81EC0584D2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"520871a883948973675d359be18ee2d4253edc57","datavalue":{"value":"http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p25","type":"string"},"datatype":"url"},"type":"statement","id":"Q426901$77566D60-D628-48F0-B60D-C9BB0A76E58F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b9edeab5ade250f1ae581823e4f707737db2d9de","datavalue":{"value":"Summary: We study the number of vertices which must be removed from a graph in order to make it planar or series-parallel. We give improved upper bounds on the number of vertices required to planarize graphs of bounded average degree \\(d\\), and for small \\(d\\) also an improved bound for series-parallelization. The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. The above bounds on planarization yield improved bounds for the coefficient of fragmentability of the class of connected graphs of average degree at most \\(d\\).As an application we give an improved bound on the size of regular expressions representing deterministic finite automata.","type":"string"},"datatype":"string"},"type":"statement","id":"Q426901$29B8064B-F01C-4EA1-AE78-848FDFD6730D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$8EC31B3B-3616-48F1-AF3E-208080867355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$27131189-9B6E-405A-A72E-220653884C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$60171728-4457-4D5D-8437-016890729C67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$85355F9E-CA04-4402-ADBC-79E73868982E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$10138BFE-1B99-4E04-B688-DF4A62DD5C04","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91c6317db11ff03c110a5e20e448cbb28d27719f","datavalue":{"value":"6045718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$1980512F-0AD5-4B59-B11F-9CADF2B9D4B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66e5f8de25ccb7bb5934d17912247086bf79b861","datavalue":{"value":"fragmentability","type":"string"},"datatype":"string"},"type":"statement","id":"Q426901$9325D7ED-51ED-49EF-B079-95F30F07A696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2be1e26ca40b1eaf4b34fcd392e6fb5a2b5d7f63","datavalue":{"value":"planarization","type":"string"},"datatype":"string"},"type":"statement","id":"Q426901$9E942AAE-DD4F-4662-BCA6-3BB241E28FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db155a1931c450924f78e9052809373e70af6db8","datavalue":{"value":"series-parallel","type":"string"},"datatype":"string"},"type":"statement","id":"Q426901$2DC81D80-A575-4267-85EB-E022E841D23F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b17e6e28d1a18f7a35b77cc1e7558e6f62021227","datavalue":{"value":"tree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q426901$A06C1FCE-DAEC-478B-8252-6937EE411CE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4369065edf6d8d2db82064ebbf82bc692ed5b6f","datavalue":{"value":"regular expression","type":"string"},"datatype":"string"},"type":"statement","id":"Q426901$D0056BC6-74AC-4BCD-B57B-7226C06F99E7","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":"Q426901$151F540D-A05A-474E-A36B-56A84FC1B1C5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"fd68a4903fb3390dde71d8e297fa1a6abb0ec856","datavalue":{"value":"bafkreihbwj47za453yllc2revcyy5ogdaebzgufg7qqmuaqjq4cbzsuvsa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426901$1D9380E4-1AE2-4BAF-ADB5-AC137A34FDCE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d25a38668dc30e6aff1d1f51f65501acdb6bd6eb","datavalue":{"value":{"entity-type":"item","numeric-id":2427499,"id":"Q2427499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"160c20a25ff57819a575b165a0b7c1f1a9426f8c","datavalue":{"value":{"amount":"+0.8239431977272034","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":"Q426901$21E95E49-8027-463D-B243-A95F13005325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15207cc5be9776da68a0582cd9a54184b28e6718","datavalue":{"value":{"entity-type":"item","numeric-id":1850531,"id":"Q1850531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd676d706d4b1e5a496a03d29cc30cc0bf0459a5","datavalue":{"value":{"amount":"+0.7876879572868347","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":"Q426901$9E7D09D0-BFDB-426B-9D87-2F8BE90E94CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c420611d850ae8734b5da3a847e8fa733de120be","datavalue":{"value":{"entity-type":"item","numeric-id":372966,"id":"Q372966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3bf9a92e38989ba7482876c4de6ae32847d017d","datavalue":{"value":{"amount":"+0.700861394405365","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":"Q426901$6F607C36-33FA-49D7-838B-5994EA0AF097","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6306320c882e8c2d0cebf2cbe1eec2bb94482c67","datavalue":{"value":{"entity-type":"item","numeric-id":3113714,"id":"Q3113714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c01d8b118af02832d4b70ce3c2e3644288e6cf30","datavalue":{"value":{"amount":"+0.7004222273826599","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":"Q426901$EED86F9B-A950-4998-A106-0D62830A7EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6c2110d9fb3d10eb2bb526f83926e7532aa63b5","datavalue":{"value":{"entity-type":"item","numeric-id":5199507,"id":"Q5199507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c53bb25ba86401dd0acf986d1d86868f3e7f0fc8","datavalue":{"value":{"amount":"+0.6934313178062439","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":"Q426901$0CC4D260-1805-4B3D-8374-770765D19682","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved upper bounds for planarization and series-parallelization of degree-bounded graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_upper_bounds_for_planarization_and_series-parallelization_of_degree-bounded_graphs"}}}}}