{"entities":{"Q1201816":{"pageid":1212565,"ns":120,"title":"Item:Q1201816","lastrevid":69874002,"modified":"2026-04-13T10:55:31Z","type":"item","id":"Q1201816","labels":{"en":{"language":"en","value":"Some results on visibility graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 98506"}},"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":"Q1201816$1F4A6FF9-FF9A-4619-ABD2-C96C61A1C3C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f827a594b60521f466fcfae63dc8290bb6d9bb63","datavalue":{"value":{"text":"Some results on visibility graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201816$B09B3B63-B8A4-4EB1-AB74-A9FDB28693FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a7713ece22ff54ed913749eefe99072bb50af0f","datavalue":{"value":"0781.05013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$779285B1-ADC1-4744-943C-5F9536867CD8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"86a025c61f84c4add663cfb241cb7d694d0fb983","datavalue":{"value":"10.1016/0166-218X(92)90018-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$AF4B0DC7-4E3A-4238-AF09-86B6A6A5F280","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ea6c9e988b1a5ccaf11509582e9469b2e708609","datavalue":{"value":{"entity-type":"item","numeric-id":689954,"id":"Q689954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$DAC12E52-AD9C-438C-83CB-A97C54718063","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$08EC5BE5-EBEE-4D45-B3BC-9CA3E32ECA28","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1201816$886134ED-5081-4A67-BE44-D1594E5B4D97","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"15f3ec33f351e0fb512bdc2a0f6241b8d46d636c","datavalue":{"value":"A visibility graph is a graph whose vertices are pairwise disjoint horizontal straight line segments such that two vertices are adjacent if and only if there is a vertical straight line intersecting only the two vertices under consideration. If the segments are allowed not to include the ends, visibility graphs have been characterized completely by R. Tamassia and I. G. Tollis: They are the planar graphs having an embedding such that all cutvertices are on the unbounded face. When the line segments must include the two ends, the situation is different as demonstrated in this paper: There are 3-connected planar graphs that are no visibility graphs, and the problem of recognizing such graphs is NP- complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201816$99900FEC-A127-4265-846D-E74A1516A861","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d393e912a87e0b6d20651d2850b1ecb3876ac6d6","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$4BCDCAFF-323B-427D-9939-A59ABED43A0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$8212F5F1-41DE-4E4D-9495-A9AAD0E6CBD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$D0EECBA7-A820-4D95-B472-0E4E819DDA3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$AE141F46-BF97-49C0-9EDC-F101A7B0DC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$432C63FA-DA7D-4E2D-AC73-78805159969B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$8D0FAE79-426B-4035-9BB4-A9FA5A1AD4AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$03BA5583-9755-4B18-944A-FB3ED57B486F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e00e6647c9a21f4717767b222c8acdd64933acdd","datavalue":{"value":"98506","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201816$87ED76D4-6781-491E-BE72-4312AF637DBF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"789386d2db874eb7c464a6c6adbdc90ff4738811","datavalue":{"value":"visibility graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201816$A3FAAD51-4C21-4CDB-90B2-DC810DF9F9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e86d9b4ad5a06064fd9c9bcbc50f8026b1c776dc","datavalue":{"value":"embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201816$F4AD3514-5963-4C1F-9F32-0796A9328B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201816$0C2C4486-98E2-41B9-A4A5-2CA2C88CB2F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201816$8B58A778-20F3-4AC5-9CB6-FC478A03E0DB","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":"Q1201816$C1DBBCF0-7975-47B8-9589-882347CFF3D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$870C9B33-14D4-4EA7-8D5B-BDF55376E0BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6749c7414b5d6466cb924bea71d7118afef2a7e6","datavalue":{"value":{"entity-type":"item","numeric-id":1124349,"id":"Q1124349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$5F1D2114-EB01-45F3-84D9-D45381DDD8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"220d4ab4bf1e85d67a96585735c0bcc184d9d730","datavalue":{"value":{"entity-type":"item","numeric-id":5586413,"id":"Q5586413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$5E02BB17-FD1E-47F4-A9C2-C8D3BAF6A2BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0a8e4ccae21ea52906e2c227811922501b04ce","datavalue":{"value":{"entity-type":"item","numeric-id":4110937,"id":"Q4110937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$264A604A-92F9-40CA-8701-BFC44BA13A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$77865DCE-3C7A-4B08-B9FA-8FBA3D6D80C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bac3c740a462f7d2ef624da580496f9988fcd65","datavalue":{"value":{"entity-type":"item","numeric-id":4028897,"id":"Q4028897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$F6B2C874-5671-4AF2-98AA-B3D236D629C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f5c77d5d4160815e22cc26fb00f80d4fa3873b6","datavalue":{"value":{"entity-type":"item","numeric-id":3735087,"id":"Q3735087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$7124C879-C4BA-44CB-96C4-6E7D3FDEFC59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$F4C37189-8A6D-4B64-86E2-A0BB7AFD3A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af72090073d5912c38dad610798f46a63f103cef","datavalue":{"value":{"entity-type":"item","numeric-id":1099193,"id":"Q1099193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$EEF5E1D8-D6D2-4A5D-8DC9-EEDA2119C308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a87849b8e35e5ed292869fc9ce052c8a6c3f658","datavalue":{"value":{"entity-type":"item","numeric-id":1114721,"id":"Q1114721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$284DECAC-286E-4B60-9625-EEFA7E4DE637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2dc51f455e8035861032dfb9491c0817f3e724","datavalue":{"value":{"entity-type":"item","numeric-id":1085168,"id":"Q1085168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$EFC7D42A-2F3D-4281-8FB3-FD989BD79007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d559325bc6d150c41f7e7c490b2a619364a89614","datavalue":{"value":{"entity-type":"item","numeric-id":1085167,"id":"Q1085167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$82751D52-11E1-4934-83AD-6C32D813CB2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f19e5e497c2616937758b2d5a9686424c48c6ea","datavalue":{"value":{"entity-type":"item","numeric-id":3785982,"id":"Q3785982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$D9E89DB9-F177-4D33-BBF0-CEF740759882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea5d13b19da03bd965188dbf676026b51b180449","datavalue":{"value":{"entity-type":"item","numeric-id":3200548,"id":"Q3200548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$502A18D0-C659-44EA-A012-056EAE106939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf76156772eb015388751b626faa593687fcf58f","datavalue":{"value":{"entity-type":"item","numeric-id":3216670,"id":"Q3216670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201816$2F90C5BD-0E27-431D-A102-D90483646576","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f38ca5c94529cdd77fd47d85908030bee2c07628","datavalue":{"value":{"entity-type":"item","numeric-id":1099193,"id":"Q1099193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce00f2efc1f7d7636bc2551f9d0f5324a4e80e8d","datavalue":{"value":{"amount":"+0.8815429210662842","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":"Q1201816$78811C74-7A12-4596-AC77-26A026B0CD27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c82f96e31f1e4aa3d2d688e84ede6deddc6db6a","datavalue":{"value":{"entity-type":"item","numeric-id":1581056,"id":"Q1581056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71bb15222caff0127ed0bb2b42c956629fa21269","datavalue":{"value":{"amount":"+0.8555236458778381","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":"Q1201816$4194DF4C-3A05-4E3E-A21F-1D72BC53B7E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73b0d1aae867cdfe4f9b6a1d83bc6d2774c6ee19","datavalue":{"value":{"entity-type":"item","numeric-id":3814827,"id":"Q3814827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3839427f7e81ca792b9b395c7845ca1f31bad23","datavalue":{"value":{"amount":"+0.850792407989502","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":"Q1201816$AB4EA9E0-5942-4FD5-993B-A338C95C2224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d55fcc1a9332f4f912be65843d54a8161fbb15b","datavalue":{"value":{"entity-type":"item","numeric-id":1085167,"id":"Q1085167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"392ffd5c842cfcff7fac2d7ea782fd6bd306bfb4","datavalue":{"value":{"amount":"+0.8254401087760925","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":"Q1201816$066B8C2F-6F1A-492A-9C7D-2F070773AAE5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Some results on visibility graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Some_results_on_visibility_graphs"}}}}}