{"entities":{"Q916669":{"pageid":918517,"ns":120,"title":"Item:Q916669","lastrevid":65358408,"modified":"2026-04-12T02:03:00Z","type":"item","id":"Q916669","labels":{"en":{"language":"en","value":"Embeddings of graphs with no short noncontractible cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4154460"}},"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":"Q916669$EE8D8D96-E29F-40B4-B065-A309C586A851","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be6c1d936f0939e7ccc4fa93f3dcacd6fb4b7ae4","datavalue":{"value":{"text":"Embeddings of graphs with no short noncontractible cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q916669$3536F6B2-4634-42C1-9D33-EEDF61D2B1F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9b733162e091c428463546aa223d12ba06acf84b","datavalue":{"value":"0704.05011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916669$2657B271-5804-4824-AF80-EA5EABDC4983","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fa0bf21f190645e7f4852623d071ce41e4e15564","datavalue":{"value":"10.1016/0095-8956(90)90115-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916669$185782B9-F794-4D92-BF4D-9AEC5E26B4ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$C9C3D5A4-2A01-4376-ABC5-6C0237CE8573","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$4C39B25A-CD62-45E8-9F6B-8B4117FAB584","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":"Q916669$22D88B5D-7766-431A-9DB6-0C0966718CA3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b890bfd73624b52e38193378abd9b5bd7f3fccdd","datavalue":{"value":"The author investigates 2-cell embeddings of connected graphs into closed orientable 2-manifolds which have the property that every noncontractible cycle has more edges than every face boundary. Such embeddings are called LEW (for large edge width) embeddings. He shows that every LEW-embedding of a graph G is on the surface of minimum genus for G. Moreover, if in addition G is 3-connected, then the embedding is unique (up to mirror- image). This generalizes the results of \\textit{H. Whitney} [Am. J. Math. 55, 245-254 (1933; Zbl 0006.37005)] that a 3-connected planar graph has a unique embedding on the sphere. Polynomially bounded algorithms are obtained to: (1) find a shortest noncontractible cycle, for any graph embedding of positive genus; (2) describe an LEW-embedding of G or tell that no such exists, for any 3-connected graph G; (3) describe a minimum genus embedding of G or tell that G has no LEW-embedding, for any 2- connected graph G. Some of these results are refined for triangulations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$3E8A9E8F-9C63-4A52-834D-21033102C155","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916669$2CCE6235-AAAC-447B-A4AF-4788D8914FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916669$D9EC238D-4409-4AD8-94BA-ADB4DD774CBA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"143f2ddfadc05d43c0af2aed0b4fc4119ebb4fbf","datavalue":{"value":"4154460","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916669$FD9663E8-AF40-4731-9655-F9ECE30BA216","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed64e79ea2cb2a8fb9b6c8929905a4f15043b8b9","datavalue":{"value":"2-cell embeddings of connected graphs into closed orientable 2-manifolds","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$9957DA54-A190-49C4-8173-87B09CC128AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2a44edb36c06fa13a4650e16159c18dd89b76d9","datavalue":{"value":"LEW","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$C6E1CC90-3DF8-4A1C-9ABE-69C8451E8A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"898dbc0694f26e3c45d3240b4129c80c90b2da58","datavalue":{"value":"large edge width","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$4A31E7D3-C4D5-42C7-A5C7-87BE05F7ABCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c81695512a2e1fea7e3398aafa7eedb400e6359","datavalue":{"value":"LEW-embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$2F727CF6-25D3-48FB-9A99-AAAEBA55A119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cc2648df1937607c7d5a6efb28994d9ce2a9392","datavalue":{"value":"minimum genus embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$749668EC-07CA-4AD8-A3B3-4C291CE7D409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88244eaf771352cc184de31279f1fe59185b88de","datavalue":{"value":"triangulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q916669$35A5B196-1E83-44FA-90E5-314BA6610B75","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"205b6d05d63e09819854956633396177079e7ebb","datavalue":{"value":{"entity-type":"item","numeric-id":591987,"id":"Q591987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$8624F111-9D08-4BBC-ACAD-00750E85A7A9","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":"Q916669$F9CEDCCA-F4E1-4699-800F-80320277D63E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ec982c40e8526e3ba59852f853a1b7688849796","datavalue":{"value":{"entity-type":"item","numeric-id":2557709,"id":"Q2557709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$20B7D583-E593-4671-9257-0D80E2743CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c837da2ca835eb3ccea4c3ff35b00c88bde3a596","datavalue":{"value":{"entity-type":"item","numeric-id":5518140,"id":"Q5518140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$45D6B7E0-876A-4832-9AAB-5CB57B8799AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade29bb9c5c58c1fc73fbff734d987495a982508","datavalue":{"value":{"entity-type":"item","numeric-id":3757929,"id":"Q3757929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$2177DB63-3115-44E6-AC53-F95A8F8D9D01","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":"Q916669$FE876F47-B1E1-4231-AA94-36018638A9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1358f603d35dc96f863ac0ca06bfb8dc56ca7127","datavalue":{"value":{"entity-type":"item","numeric-id":3317125,"id":"Q3317125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$9A885E75-3E12-495D-898F-76336CF23C45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"855b1b40b5b52fe3f5b2c82ae3034d554e99c3bc","datavalue":{"value":{"entity-type":"item","numeric-id":1088996,"id":"Q1088996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$D6C9120A-7541-46DD-9B76-758FB2FF3081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3b42dfbd11923da06818a3556f6a4fd02532e18","datavalue":{"value":{"entity-type":"item","numeric-id":1837698,"id":"Q1837698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$B2B0B31C-2F13-402E-A8C3-C24F0CC3C63C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c63b7be2260467f86c6dce43eedea3919e54774","datavalue":{"value":{"entity-type":"item","numeric-id":1053703,"id":"Q1053703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$0F9BB21A-84B7-4971-8D8D-73AA9E593C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41d49e608d5ffc8abc77bd4e4e561119c3c473e","datavalue":{"value":{"entity-type":"item","numeric-id":1142781,"id":"Q1142781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$ABD6B651-3986-4C73-90BE-26FC8E96BDEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99023787a83dcf1a612098c5c898fa15b9ba3c9d","datavalue":{"value":{"entity-type":"item","numeric-id":3031932,"id":"Q3031932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$B1DB0FB4-6517-46CA-9118-392D77C79A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d990a995876f36f7ec1a091c259d6d4e2b928d58","datavalue":{"value":{"entity-type":"item","numeric-id":5724435,"id":"Q5724435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$D1366626-945B-4213-B723-DF719BA88C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d293875dfd3c5270042fd0d97947b12e7c0acf2","datavalue":{"value":{"entity-type":"item","numeric-id":4273853,"id":"Q4273853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$3993FF84-0D70-49F4-9CE9-D2328018C031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"325afa4e4e5e0510f3b0f0715c6549cac3c1fd16","datavalue":{"value":{"entity-type":"item","numeric-id":5684700,"id":"Q5684700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q916669$67F366BD-9F62-4239-B009-0F67D297954C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d663f466389705f58586107baf92bc54e1039d9e","datavalue":{"value":"https://doi.org/10.1016/0095-8956(90)90115-g","type":"string"},"datatype":"url"},"type":"statement","id":"Q916669$541E1D6C-F25D-468B-A689-858BBA33FED2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2fe976706328606ec46fdd00bad41bd5cbd2a626","datavalue":{"value":"W2025861110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q916669$8BC55552-5859-4331-86AD-63059760D812","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c1e73a01e7ef39f8a71581e3a256cb0b3f887ca","datavalue":{"value":{"entity-type":"item","numeric-id":3642286,"id":"Q3642286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdbfe391365b6d85a063fdead789a3b83d1f6b20","datavalue":{"value":{"amount":"+0.8531899452209473","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":"Q916669$DC2B1B40-3015-4741-92B8-CEE483C4C841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"303d0f5432a5f504c0ce26bd0d2c6048bd6cf94e","datavalue":{"value":{"entity-type":"item","numeric-id":4672591,"id":"Q4672591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67183314bec7959721d7de5af9b682ddf8c48470","datavalue":{"value":{"amount":"+0.8258963823318481","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":"Q916669$857E1F5C-0969-4933-9F86-FF24FE2CA885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e07519d5bac9cc340d54a36893d730ae40679f6","datavalue":{"value":{"entity-type":"item","numeric-id":419374,"id":"Q419374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b57597e8a785e6c6d006de597faaf73995bc1943","datavalue":{"value":{"amount":"+0.8085018396377563","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":"Q916669$DEAE25AE-9DCA-4236-8478-89448420385F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f04d6b1dbcc2dded6ae2e3a679d714a77db25783","datavalue":{"value":{"entity-type":"item","numeric-id":878074,"id":"Q878074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8955a14c885525ddc29aad2ed550ad166fc4f66","datavalue":{"value":{"amount":"+0.8041383624076843","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":"Q916669$2E927953-4B3D-4F95-BB95-0663300609E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7fcf0ba6ca71551feb16dcbcd74367219910944","datavalue":{"value":{"entity-type":"item","numeric-id":3813826,"id":"Q3813826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1492723eae3ce3d60cda7e818b3ae473fca8e44f","datavalue":{"value":{"amount":"+0.8022544980049133","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":"Q916669$5D39E941-ACD6-4C73-9525-944F77B372B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Embeddings of graphs with no short noncontractible cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Embeddings_of_graphs_with_no_short_noncontractible_cycles"}}}}}