{"entities":{"Q1338319":{"pageid":1349058,"ns":120,"title":"Item:Q1338319","lastrevid":47284174,"modified":"2026-01-01T05:52:51Z","type":"item","id":"Q1338319","labels":{"en":{"language":"en","value":"Intersection graphs of segments"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 696914"}},"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":"Q1338319$636CAF63-7B60-4BD4-A0E7-22DD4E58FEA4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35fa639e2bb283e6c864b142e6154eac064e2a6e","datavalue":{"value":{"text":"Intersection graphs of segments","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1338319$FA86A508-16FC-42E5-B8B2-D6DD2AD2E3E8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4af0ab72ebc5321307b2f77899917924932274ce","datavalue":{"value":"0808.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$D028DF0E-75F7-49DD-BF6D-492C5867426B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338319$0DD4AFE2-1BF3-4707-AF24-2B71D284D829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5205659b4c2831752a8f8604dc5b3ce7b9439fa","datavalue":{"value":{"entity-type":"item","numeric-id":818688,"id":"Q818688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338319$B779D4D0-BE56-4197-A7E4-566F9F0DCF7C","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":"Q1338319$95FE487E-9E21-426D-B858-063E10EC807A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7c5bb3baf1209a5aa9c138fee26da270a964d4a2","datavalue":{"value":{"time":"+1995-01-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1338319$C8817585-DC61-4B0B-989B-F343DE84AF62","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2c09dd881b44bb9515d9b875dfb650bc500875c1","datavalue":{"value":"Intersection graphs of segments (the class SEG) and of other simple geometric objects in the plane are considered. The results fall into two main areas: how difficult is the membership problem for a given class and how large are the pictures needed to draw the representations. Among others, we prove that the recognition of SEG-graphs is of the same complexity as the decision of solvability of a system of strict polynomial inequalities in the reals, i.e., as the decision of a special existentially quantified sentence in the theory of real closed fields, and thus it belongs to PSPACE. If the segments of the representation are restricted to lie in a fixed number \\((k)\\) of directions, we show that the corresponding recognition problem is NP-complete for every \\(k \\geq 2\\). As for the size of representations, we show that the description of any segment representation, specifying the coordinates of the endpoints, may require exponential number of digits for certain \\(n\\)-vertex graphs. One of our main tools is a lemma, saying that given a representation \\(R\\) of a graph by segments, one may construct a larger graph whose each segment representation contains a homeomorphic copy of \\(R\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$23739D84-2807-4D73-BC4E-51844472A3D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$9F7BA422-52A3-44F2-AD67-863DBD6618D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$07890B87-93DA-4E5A-9233-C82C8E2599C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c51c87f5a52dc4b7e4823ab64d63e9230f97b8a9","datavalue":{"value":"51M30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$F6E38CFE-8D91-403F-BC3D-14FAE8BB92A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$023656BB-B84C-431C-B36B-BED9F7C73EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$B9DE6FD4-E360-4482-BD4F-846CE8640C91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f45e8c911d4ec76415a359f3c02e212a8977dd74","datavalue":{"value":"696914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$CC737EC1-39EE-4162-BFA9-D09D2B0BE5A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$200BFF0C-E999-4925-99DF-4DDE687C4765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98350a49bfc57cca35d54e10e3920384923dd18d","datavalue":{"value":"segments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$C4F76F84-B50C-440F-940D-6C55178D59EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a2a5aaf2813613e191091bab6a7937bd2f6db3d","datavalue":{"value":"membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$B333EC66-F519-4B7E-ACED-10292E6D78BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9891227b3d7ca9f091fdc17473271d45c5e2f962","datavalue":{"value":"recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$FBA4253E-58C3-433F-A5A7-63988BA018DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33801edbdec5d6b5afd01411611b0906c147ba98","datavalue":{"value":"SEG- graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$8A22F16F-A579-4711-9A76-1A330E2B0A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$76748E08-7A74-45E2-B866-EA13AB949B22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a02e7bbbb2a6fb98a5a1bd31c69ed022d5319717","datavalue":{"value":"polynomial inequalities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$1160F344-0FA8-45A4-AEC8-22A959BFD5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b55ee0e9ba5e6c4ff2592d783b812d17aa91201","datavalue":{"value":"decision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$5EFAAB4C-D458-4C32-B7EC-E7057F15D37C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51c0410216f6db1f0aaf7ec78f4b1eb7c20b723a","datavalue":{"value":"recognition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$215962F4-80E2-4D17-81CB-B30E1D0F2DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$A6EE1D60-C9D3-4106-866A-0107A6C8846D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"444e5ac2b98cc02ca56cc8109fac5205af03b426","datavalue":{"value":"segment representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338319$E7D8238B-39CD-4515-B1C9-1B56A2883DBA","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":"Q1338319$4138DAB2-DFD8-4EA0-A5C5-053F320664D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d456f11dad4c47aaa5f68b02cd41b7824170d7a0","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1071","type":"string"},"datatype":"url"},"type":"statement","id":"Q1338319$EF662111-2E78-4152-8AED-3670F83D7867","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa7ea21f36c91d36cfdf388eaddf3e1b1d1a2b98","datavalue":{"value":"W2006753964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$FD8E927C-AB12-4BC5-935B-0F628312CAE2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"390fa73675a95a8b2a0c49c44d628420e7bfa746","datavalue":{"value":"10.1006/JCTB.1994.1071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338319$2424D733-2611-4612-8CB6-A04A3F6645B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aef5794aa66413ec6482b5ab43de9fa3c5eb56b","datavalue":{"value":{"entity-type":"item","numeric-id":5937922,"id":"Q5937922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5264f1504cc9f16febb08cd5d3ffbbc4ac147216","datavalue":{"value":{"amount":"+0.8173956871032715","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":"Q1338319$48A892E0-6A7C-44F3-A1D6-0A89222958D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf2d8738871ba9caea7ab621396b3436061b0c09","datavalue":{"value":{"entity-type":"item","numeric-id":1687911,"id":"Q1687911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36fd8ac50f62dd8e63f118ea2667caefa1dc9166","datavalue":{"value":{"amount":"+0.8154228329658508","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":"Q1338319$BA1AEBFB-6B84-413B-B28F-C8CDE3B20CDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"912e0264112f89ec8e3b9518d10292cdd7f9cfb5","datavalue":{"value":{"entity-type":"item","numeric-id":3073689,"id":"Q3073689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac58c55e13f7db11e9df09d2be62a2161593ed1c","datavalue":{"value":{"amount":"+0.8142062425613403","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":"Q1338319$C26DA108-200A-4394-A3FF-0DF5C0B02BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3aba89299de85b4cf312a746d6f018c2e866d118","datavalue":{"value":{"entity-type":"item","numeric-id":3348944,"id":"Q3348944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd5cd138ae99294ce0487127f19ab88421c9d22b","datavalue":{"value":{"amount":"+0.8126119375228882","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":"Q1338319$E1111909-021B-49B7-9552-5A9765FB1FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cc022ce2f0805a66fae402067402720f184d90a","datavalue":{"value":{"entity-type":"item","numeric-id":4585058,"id":"Q4585058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8e54b6e60583efef6a98a63d8f0c04437b143c3","datavalue":{"value":{"amount":"+0.8100146055221558","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":"Q1338319$6FDE6990-ADD6-4AC4-9B4B-65F75277F282","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1338319","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1338319"}}}}}