{"entities":{"Q1103631":{"pageid":1114383,"ns":120,"title":"Item:Q1103631","lastrevid":67000764,"modified":"2026-04-12T14:15:15Z","type":"item","id":"Q1103631","labels":{"en":{"language":"en","value":"On embedding graphs in trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4053645"}},"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":"Q1103631$376D6275-22B1-4E80-8B9A-3DBB7BF13D5C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"855b93867ca1b161ce75475ac6facf3471c46828","datavalue":{"value":{"text":"On embedding graphs in trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1103631$02621A6D-8FB4-4224-8BC8-5B9A3B875D33","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d8f96bd7d4dd4c191c75727e34bebd628a3c6e2c","datavalue":{"value":"0646.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103631$7580CB60-EF12-49BD-8488-7CC9CFD0C72D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8e58d6e8db55b2e30b8aaadf6c18e31a35b060c1","datavalue":{"value":"10.1016/0095-8956(90)90066-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103631$91254AE8-F2B6-454C-B6B4-2128ADBACFFA","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":"Q1103631$8D9A42BE-5FD8-4007-9810-A7F46A4E9D2C","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":"Q1103631$8D8D9876-B3FD-4D28-ACA3-DBF70D25C0CC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b95f3b1439ec310e98738c337e42ec6f20a25f10","datavalue":{"value":"Let G be a graph of small maximum degree, which is contained in a chordal graph of small clique number. Is G then contained in a chordal graph of small maximum degree as well? This extremal problem arises from the following: suppose we seek a binary tree T and an injective mapping from V(G) to V(T) (and which sends edges of G to paths in T) so that we minimize (1) The maximum overlap, over any edge of T, of paths corresponding to edges of G (known as congestion), or (2) The maximum, over all edges of G, of the length of the corresponding path in T (known as dilation). We show that the congestion is controlled by the maximum degree of G and its tree-width. It is in comparing congestion and dilation that the chordal graph problem arises. The answer is ``yes'' for graphs of small genus, and ``nearly yes'' for all graphs (the dependence of the best maximum degree on the number of vertices of G is at worst very weak).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103631$5983484B-3F94-4010-BF0F-1A525C12288B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103631$060A3A83-B6CD-4A3D-A44D-389222983C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103631$49933BA1-0B93-4232-B530-2502D950E845","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54547f418571e5c920496fe895a168d8f1f7e5f8","datavalue":{"value":"4053645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103631$7E46D111-14B4-41C3-ACE3-12ECECAB878B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103631$6CE9F3AD-A8C1-406F-8137-31022FDB772F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15b4a7e94f67b1256fa87c9c444c77ea9a3d63a5","datavalue":{"value":"graph minors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103631$7ACBFFA5-751C-4FD4-BB79-D7623D7D5F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103631$5BBF19D1-A072-470F-98DD-CD45B5286B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb6f1baff13cdf595fcb305c4ff855a183d79876","datavalue":{"value":"graph embeddings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1103631$1E35B3EA-030B-4578-8A37-60AB4249B7F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db91f50b8be0377b16c54636f8603d4272be2cda","datavalue":{"value":{"entity-type":"item","numeric-id":163023,"id":"Q163023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$830F6923-9848-4D96-874C-A6A5900C9BB5","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":"Q1103631$99460382-65CD-4C2E-A663-32489035BC2C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"de05e1318518ed7baa44ef7627b01f66f7535451","datavalue":{"value":"https://doi.org/10.1016/0095-8956(90)90066-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1103631$78516CD4-6E25-45A0-A61D-DBEDB52DD050","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"62cd9812b1a61a0871f03539417b32351f03b911","datavalue":{"value":"W2012917738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1103631$6D2FD7FF-82DB-480E-806F-BC8D701D0126","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$DF5171B6-7C2A-4B49-B5C8-424AAB0F5F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ab44c38234842ff7992ba00e47b9713793ea09","datavalue":{"value":{"entity-type":"item","numeric-id":3782808,"id":"Q3782808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$8A2FDEBE-2347-4C99-911A-0082722ECC0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d823bde0afa959f545aa85998f405220b941317","datavalue":{"value":{"entity-type":"item","numeric-id":796306,"id":"Q796306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$11A4A680-CD13-43A8-9433-6AA1FB4C348F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"468123f607fe9c0a7affbe6709664ebec53c9057","datavalue":{"value":{"entity-type":"item","numeric-id":3956994,"id":"Q3956994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$E7E0B26D-3133-488C-A85A-E14D42AC184F","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":"Q1103631$1FDAFB0C-8D2A-4C98-8BC5-FA91CD0260E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bfca8d74ac085074d3fdc3c376a602f25e71f42","datavalue":{"value":{"entity-type":"item","numeric-id":3763589,"id":"Q3763589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$9AC4A25D-C698-474A-8147-D85B6CC7FAFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b279fbd0caed565b76fad6f1a2cf4ed50d435368","datavalue":{"value":{"entity-type":"item","numeric-id":3951561,"id":"Q3951561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$C8867A5E-49F4-4DF6-B379-94E5056A3D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a36280cd96bc89546cd4961fcd5cd6aa3fbe4691","datavalue":{"value":{"entity-type":"item","numeric-id":3661483,"id":"Q3661483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$86FDB7DB-1734-47CE-8BDE-77EB79BA09C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01ad9aadd446c6d5909b1353a38646e3156d4817","datavalue":{"value":{"entity-type":"item","numeric-id":3691781,"id":"Q3691781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$F51A6760-DE1F-4008-B8B8-B175720EE056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7489661d0c92ad040adf8d2140d5b6efc776b644","datavalue":{"value":{"entity-type":"item","numeric-id":1055450,"id":"Q1055450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$7D697295-3AE8-4343-86C1-E1F43A032B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ef0f89b3d4848285d16b9f024f89d4a5e76a218","datavalue":{"value":{"entity-type":"item","numeric-id":799684,"id":"Q799684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$744F343D-4BAB-4B60-AF22-CAE262A1B0C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e62926166610e171255ba7600cdacbb982331e7","datavalue":{"value":{"entity-type":"item","numeric-id":1179473,"id":"Q1179473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$7629DA10-7975-4C2C-9C6A-ECC85287EA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0f6dd793166a567719b2fb5d958eb883aea03d","datavalue":{"value":{"entity-type":"item","numeric-id":1079583,"id":"Q1079583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$C55E91C2-3D9A-4AE0-97BC-1DE994122182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9cd5ab2b4dcc204e3d6bd923419ed31e399a96a","datavalue":{"value":{"entity-type":"item","numeric-id":1079580,"id":"Q1079580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$DA78C4B2-69E1-4434-A65B-A29F75908A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83d0491bc9208f4f062dd61d3f5f857a865db72","datavalue":{"value":{"entity-type":"item","numeric-id":3785979,"id":"Q3785979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1103631$FC4AAA2B-880E-43E1-8C16-B70060A26AC6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a068a382beb96ad79bdc66982810cfd3b65c8872","datavalue":{"value":{"entity-type":"item","numeric-id":1209372,"id":"Q1209372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67713e3a6a16a9f5d8e987e85632660fb9beb7c8","datavalue":{"value":{"amount":"+0.8655753135681152","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":"Q1103631$ACFCDDC5-AC13-48BD-842E-2385569CBCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5e95f73ce4f131b608c5d3dc45509ee8682912b","datavalue":{"value":{"entity-type":"item","numeric-id":4540091,"id":"Q4540091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9d5b5e6789d4cf06385e41b08d6ed3643728f94","datavalue":{"value":{"amount":"+0.8653461337089539","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":"Q1103631$A36B7A44-6558-4C45-A610-BDB46A6AF7A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b564edda7d16e4f62000f5d5b16811ef88b6bb7","datavalue":{"value":{"entity-type":"item","numeric-id":952638,"id":"Q952638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9f9e8e53380078601e5b43b641b40a084989027","datavalue":{"value":{"amount":"+0.8380366563796997","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":"Q1103631$D3AB16EF-16D2-4558-BB29-9A864381E126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0b9f3b05da5b92bbc228bafb18df9ef1ce1c9b7","datavalue":{"value":{"entity-type":"item","numeric-id":4254358,"id":"Q4254358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bddcb68279a2c8992429d68cfc86dd0f0e03c4df","datavalue":{"value":{"amount":"+0.8331142067909241","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":"Q1103631$0AC08DAA-3BD8-4B40-8C97-1B3B656A5AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6f9e1cebaebb5b486738c668399c90b4611c7f4","datavalue":{"value":{"entity-type":"item","numeric-id":4651924,"id":"Q4651924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfcf4685eb268949aaa3aec4e624bdeb353d3273","datavalue":{"value":{"amount":"+0.8219032883644104","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":"Q1103631$E291EA29-1880-4A16-9181-CA1A9777BF35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On embedding graphs in trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_embedding_graphs_in_trees"}}}}}