{"entities":{"Q1902273":{"pageid":1913015,"ns":120,"title":"Item:Q1902273","lastrevid":73724835,"modified":"2026-04-14T17:03:00Z","type":"item","id":"Q1902273","labels":{"en":{"language":"en","value":"Fill-in and operations of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 817800"}},"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":"Q1902273$D5B45C6B-61AB-4F31-BDC0-056080DF3B62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bad4b326284c1ad43bd3e1fe9d221eb146c3677a","datavalue":{"value":{"text":"Fill-in and operations of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1902273$BD837BED-717E-4EC0-A1FB-25918B315646","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6573c54dc8ea178383a20ee79480afa0c6134bff","datavalue":{"value":"0835.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902273$BDDF61CE-31F3-4AA0-B4E6-E97C523C84F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d70565714f38c0cb96e85c14fdd2dbb0790eda0a","datavalue":{"value":{"entity-type":"item","numeric-id":215029,"id":"Q215029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902273$CA40C093-4514-46AF-804D-FDDF6ABF0F53","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"458fca2b56f2582953e7095ef1b99c53dd52a001","datavalue":{"value":{"entity-type":"item","numeric-id":547811,"id":"Q547811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902273$87DEB758-065F-4CA5-8196-A885DC06EBA6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df778dfa1d6f480f71e5d278ca30a57130511b0b","datavalue":{"value":{"time":"+1996-04-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1902273$1B4E3564-5D42-41FB-B9F4-26FD90DF818E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"297e852c0cdf9748977f5250630171426957367a","datavalue":{"value":"The fill-in of a graph \\(G\\), \\(f(G)\\), is the minimum number of edges that must be added to the graph to make it chordal. In this paper, some properties of the fill-in of graphs are derived. The composite graph of \\(G\\) for \\(H\\) is the graph \\(G[H]\\), obtained from \\(G\\) by replacing each vertex of \\(G\\) by an isomorphic copy of \\(H\\). The paper expresses the fill- in of \\(G[H]\\), where \\(G\\) is chordal, in the fill-in of \\(H\\), the number of connected components of \\(G\\), and the number of edges of the complement of \\(H\\). Also, if \\(H\\) is a complete graph with \\(n\\) vertices, the fill-in of \\(G[H]\\) is \\(n^2 f(G)\\).   A strongly planar graph is a graph that does not contain a wheel with four spikes (the graph obtained by making a vertex adjacent to all vertices in a chordless cycle of length four) as a minor. The author observes that every outerplanar graph is strongly planar. One can also observe that every graph of treewidth two is outerplanar. An algorithm that computes the fill-in of strongly planar graphs and that uses \\(O(n^2)\\) time is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$AF644D10-A124-48C0-ABCB-D1BDDF853780","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902273$D9B4AB98-0E47-4A3D-8D43-63B5124D24D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902273$114EF6A6-4C39-4467-B473-A926156631F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902273$33665311-9EDD-47E0-99AB-4DA5678CD236","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7d5e3a444e1ff783021b45581dac86c9c959f4f3","datavalue":{"value":"817800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902273$E9A38565-4D81-4E2E-A118-17856C7402B2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5e0efc4f8a493a83621197dde220ef2095ad9db","datavalue":{"value":"fill-in","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$EC41B22F-B3D9-4956-AF4B-A31E58B70B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a2c23e7b5045b39d36f32f84f1bc8eed84eb228","datavalue":{"value":"composite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$1FAAE60C-2F9D-4EFA-9686-15757CBFB156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec6f6a8fd3b46cdc350ba7d7aa761ecd9fe6d532","datavalue":{"value":"strongly planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$EE31E528-6819-4055-A044-17072167A696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75f113a56dfa87e9ee95d74e9d49057fd46efaeb","datavalue":{"value":"wheel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$7CAF839F-724A-49C6-AA80-770A75BF3331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6d9ec77b0669b77734b6831d672122e99e5245c","datavalue":{"value":"minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$F6D259CA-8C57-4285-A985-C1638AAF8E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3801589e3f1cac737b9dede93572ceb157c30bc4","datavalue":{"value":"outerplanar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$E5BDADF8-4089-4347-B981-CEAC6D8A877D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$6B23523A-00D3-431E-9EC4-61EBE77990A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902273$A46A328A-D0DB-40B9-BD20-4E37CE8BF060","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902273$D181D28B-DA5C-4056-9969-E41D575E3FC3","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":"Q1902273$D8F00884-B318-47A1-9813-F0A3689A7A78","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c982028c062a7d5a0f24c27fe12d5e06ff36d9a5","datavalue":{"value":{"entity-type":"item","numeric-id":1910534,"id":"Q1910534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ec3c6f8daef11b36cc49826c3545c8187e2102d","datavalue":{"value":{"amount":"+0.8116718530654907","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":"Q1902273$E15DC5DD-6B8F-4087-81C5-38EB34DFA4D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d884e5cf21c7843101395d3328dc3df95774d99b","datavalue":{"value":{"entity-type":"item","numeric-id":5490487,"id":"Q5490487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"036b0aad65db530b559627d560f753e272ef653e","datavalue":{"value":{"amount":"+0.7993321418762207","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":"Q1902273$308A73CD-512C-4067-83CC-C8CBFD143D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fecdc224c066a26b373c20404830461a1141833c","datavalue":{"value":{"entity-type":"item","numeric-id":3839555,"id":"Q3839555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4a73cbbc6008c17f95027138d9d02cdab01c746","datavalue":{"value":{"amount":"+0.7737224698066711","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":"Q1902273$82DA444C-784E-4FB4-B453-E60ED1077A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"326273aa8fcb2e5460f0b0b51b3a1d644f5c5375","datavalue":{"value":{"entity-type":"item","numeric-id":5319393,"id":"Q5319393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39100c0830a62c3191b2795e487654db3e97681d","datavalue":{"value":{"amount":"+0.7435009479522705","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":"Q1902273$8F761D90-4F77-4A93-81E8-EE9B43533682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"929582d9413215399182926f570621e7c82d2608","datavalue":{"value":{"entity-type":"item","numeric-id":4232801,"id":"Q4232801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"070c7b49c29a9128faef1aa329281ed3dd073de7","datavalue":{"value":{"amount":"+0.7398579120635986","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":"Q1902273$1500FEAD-7927-4A46-9379-C7A5B187A299","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fill-in and operations of graphs","badges":[]}}}}}