{"entities":{"Q582121":{"pageid":583888,"ns":120,"title":"Item:Q582121","lastrevid":49341220,"modified":"2026-01-07T00:06:23Z","type":"item","id":"Q582121","labels":{"en":{"language":"en","value":"Extending planar graph algorithms to \\(K_{3,3}\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4130043"}},"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":"Q582121$3D56B0D7-5A73-4BB9-9D6B-D9A098B5494A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9048a9a3e129849ec36a92193db946a67afecf78","datavalue":{"value":{"text":"Extending planar graph algorithms to \\(K_{3,3}\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582121$D19AE79F-F458-43F4-BC80-59C591B81ABF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6db67c35d04e4ec1c5c0d116d0aece72da1a9158","datavalue":{"value":"0689.68091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582121$1BEC4A87-A7CB-458C-B4FE-4D6444085B80","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7ffae66671e114294542d161c4cc7f0f6789ffe1","datavalue":{"value":"10.1016/0890-5401(90)90031-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582121$713A0C41-4979-43DD-BC36-18A7DE4F83A0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f496316b317a1071c5b5dfba5a175583d61d254d","datavalue":{"value":{"entity-type":"item","numeric-id":194031,"id":"Q194031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$815E0D9E-B8BA-4111-8095-926F451148AD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$0C53AEF4-2010-49C2-B4D2-EEE1472345AC","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":"Q582121$83A81B85-592C-42B7-9914-0536AC2F0ABF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f88bc5b2b210da11f3c69d29f91906df537599e","datavalue":{"value":"For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. We extend these algorithms to \\(K_{3,3}\\)-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are: graph coloring, depth first search, and maximal independent sets. As a corollary we show that \\(K_{3,3}\\)-free are five colorable (this bound is tight).","type":"string"},"datatype":"string"},"type":"statement","id":"Q582121$BF61A720-D7EC-4BA0-9209-AEA8D83AFA72","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582121$101CC8FC-A942-48C4-BBAA-13C3573E494A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582121$81D7329D-CBA4-4712-B01A-8139D56AB8D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582121$4C3F45B5-F8C0-4070-881C-49092D8FC94E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a6df540d125ec6cc91f03c711b9e5d885b9c41a3","datavalue":{"value":"4130043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582121$E604FEF5-113F-4DBC-AEF6-D017E63B85C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0460a0356485c287af14e0288dac62f7c6b389e4","datavalue":{"value":"CRCW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q582121$C7D190DD-A22A-42DC-8582-56EBC59C783D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q582121$48EBE05E-4EF4-44C8-954A-C7CB606FA0F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q582121$CE53726F-2A91-4CD3-8425-79DD83FEFD87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"618b7b4529f3e6f820c6bc9ffeaa17a7d6c28978","datavalue":{"value":"depth first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q582121$6D611193-6935-443E-8579-428C06EF57D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb57420dd71db1ad1884f030e06200cd4ce964c1","datavalue":{"value":"maximal independent","type":"string"},"datatype":"string"},"type":"statement","id":"Q582121$F63ADBEB-22BC-4195-9DF0-A0C210FB3535","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":"Q582121$D01B3143-05FE-4184-B3D8-15A944B144EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5b29e8dddaf3838e2ed77b182b2738f0c5d0410","datavalue":{"value":{"entity-type":"item","numeric-id":1104756,"id":"Q1104756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$85214326-C461-4537-9451-8B9B82CE4C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86187cd049bd6565ddbc4e21f37dc55f378bee76","datavalue":{"value":{"entity-type":"item","numeric-id":1250223,"id":"Q1250223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$A9D837B6-C988-4C35-9DBC-21C22E541F53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"491950cd634035e7fd95f4062271456f77492b49","datavalue":{"value":{"entity-type":"item","numeric-id":1062457,"id":"Q1062457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$6D39B6FC-099B-414F-8884-688FD7E857F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e03a89f076ddac2527370fc1cfe91fe5299e9ee","datavalue":{"value":{"entity-type":"item","numeric-id":3917502,"id":"Q3917502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$0440D022-AD4F-4E43-85E9-5EF6BD01EA03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"537f1c0b5db5c3a1b78043d93e8bbdf6fdd6f277","datavalue":{"value":{"entity-type":"item","numeric-id":5837296,"id":"Q5837296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$90F6AC63-4BEA-4CEC-A02F-A0268D61D43D","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":"Q582121$A4C608AF-02E8-4434-9EDA-00A9FFB92A80","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":"Q582121$AFD3AB43-A304-4248-B038-F324D314062A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b870ff096cd9b7374b71a9c8fe8f62feec4207","datavalue":{"value":{"entity-type":"item","numeric-id":3219752,"id":"Q3219752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$212EED31-1535-4C09-9DEC-3CC2C774185F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b3023ab2e96c7839c0565934faddc8d14acbd4","datavalue":{"value":{"entity-type":"item","numeric-id":1085169,"id":"Q1085169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$1A89942D-801A-47C4-94AB-50304E685D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b7f421571a2d71ea5ce0028ff1487f50f83aed","datavalue":{"value":{"entity-type":"item","numeric-id":3753502,"id":"Q3753502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$5D34035F-A502-44A0-98CE-840461B0D3C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d65e5fa96c04c984fc37232aa1378e70a7f1aba2","datavalue":{"value":{"entity-type":"item","numeric-id":1120597,"id":"Q1120597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$CE2799CA-C464-46DB-8F93-245E0D3DE764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1265334c97f9278fdebf22ec46b939a0e44b551","datavalue":{"value":{"entity-type":"item","numeric-id":3798262,"id":"Q3798262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582121$B3322833-A0B7-42E2-A695-BC6E47DBD935","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"074a4469185e8727a4f60717246ccbb2530a5590","datavalue":{"value":{"entity-type":"item","numeric-id":3817629,"id":"Q3817629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f42a60ddc11b70092e300173405c2e9da2f71f0","datavalue":{"value":{"amount":"+0.9984860420227052","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":"Q582121$57F536FC-0240-40F2-8569-823BED6A32BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54338429b7bbf25fd66a7f86e2864f61bb850a51","datavalue":{"value":{"entity-type":"item","numeric-id":4540065,"id":"Q4540065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2b305b7f086d4d8b36b3c88539b6352540905b6","datavalue":{"value":{"amount":"+0.7783417105674744","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":"Q582121$8656F14E-BF30-4DE1-87DD-DE39DE4EE2A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bd45c1e7ac18348dfd286415916d437f3a023d5","datavalue":{"value":{"entity-type":"item","numeric-id":4377126,"id":"Q4377126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b02a5b2f05c19aec6cd436ee57f9c6349bd2404a","datavalue":{"value":{"amount":"+0.7739059329032898","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":"Q582121$36D28561-622B-4C88-87FE-EF3BE8BF84A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49b4d8038f1f90e10733180a239f7df55dac0a31","datavalue":{"value":{"entity-type":"item","numeric-id":3438969,"id":"Q3438969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8397817f2cf3888985ea5666b8f907f5ab7f118e","datavalue":{"value":{"amount":"+0.7691563963890076","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":"Q582121$9CF71CD6-FDB1-4BD9-A72B-581A593505F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa5f8d00ec5f77368ab0c1e80bbc93abad3ad9d4","datavalue":{"value":{"entity-type":"item","numeric-id":5741779,"id":"Q5741779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85ab22d31071b40c974c0b9c9aa0eee11b64c243","datavalue":{"value":{"amount":"+0.7678057551383972","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":"Q582121$6992DB6C-51CD-4A41-BB65-A64FEAF3473C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:582121","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:582121"}}}}}