{"entities":{"Q1310234":{"pageid":1320984,"ns":120,"title":"Item:Q1310234","lastrevid":67133820,"modified":"2026-04-12T15:31:08Z","type":"item","id":"Q1310234","labels":{"en":{"language":"en","value":"Abstract sphere-of-influence graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 475043"}},"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":"Q1310234$005CB26D-3B1D-4B1F-8CA0-B5125A473477","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4dbc4238ec3731e212d278d04514130470baead3","datavalue":{"value":{"text":"Abstract sphere-of-influence graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1310234$C7B760BC-6C08-4F65-8300-792F41F331BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c3e632316b672a5fa4d291243974694390931285","datavalue":{"value":"0791.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310234$6491E3C1-1E94-4D93-9AB5-0639C2E53908","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cd75fc126070a444baf8fb0728ebf85a0ababb1e","datavalue":{"value":"10.1016/0895-7177(93)90257-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310234$2FB692FC-4707-4056-BD00-A96387ABB191","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06d35deff844ad14009ec831196ab8a1bd18feeb","datavalue":{"value":{"entity-type":"item","numeric-id":293362,"id":"Q293362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$C5019E3F-5C7E-43E2-B7BE-0F56D98C0E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cb08b9888d4594b9506754577c43eb23e5f2820","datavalue":{"value":{"entity-type":"item","numeric-id":185068,"id":"Q185068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$FAB605BC-A784-46E5-8EAE-AD1076AA2F84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8cb1c0d1058980e6b2795485ab4f68acb07de267","datavalue":{"value":{"entity-type":"item","numeric-id":294707,"id":"Q294707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$89F38F0E-ED46-421B-9F0F-BFEDBE01F1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d53e7573e2127761b3602ccbad94b92a28a555a2","datavalue":{"value":{"entity-type":"item","numeric-id":734370,"id":"Q734370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$AEEBF136-9769-444F-8EA8-E2093F7413DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b010567da0e068295e34b824b5eafea5ffd18ef1","datavalue":{"value":{"entity-type":"item","numeric-id":166953,"id":"Q166953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$77E00143-B049-4ADE-9400-279AE7F07B8B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7223387519d97cadd17a53db6e468e89edace165","datavalue":{"value":{"time":"+1994-07-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1310234$E666AE0C-3110-45D3-AFFC-60BCC3322DDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ccf816d7bc4b32481f0789766c7003220f1f328","datavalue":{"value":"Let \\(S\\) be a finite set of points in the Euclidean plane. For each \\(x \\in S\\), let \\(r_ x\\) be the smallest distance from \\(x\\) to any other point of \\(S\\), and \\(B_ x\\) and \\(A_ x\\) be the open and closed disks (respectively) of radius \\(r_ x\\) with center \\(x\\). Two graphs \\(G(S)\\) and \\(G^*(S)\\), called the sphere-of-influence graph and the closed sphere- of-influence graph, are defined on the vertex set \\(S\\). There is an edge \\(xy\\) in \\(G(S)\\) iff \\(B_ x \\cap B_ y \\neq \\varnothing\\) and \\(xy\\) is an edge in \\(G^*(S)\\) iff \\(A_ x \\cap A_ y \\neq \\varnothing\\). A graph is called a SIG (or CSIG) if it is isomorphic to some \\(G(S)\\) (respectively \\(G^*(S))\\).   This paper presents several elementary results on SIGs and CSIGs. Thus all \\(K_ n\\) with \\(n \\leq 8\\) are SIGs and CSIGs. While every path \\(P_ n\\) is a SIG, it is a CSIG iff \\(n\\) is even. Also every cycle is a SIG but only \\(C_ 3\\) and even cycles (among cycles) are CSIG. No star \\(K_{1,n}\\) \\((n \\geq 3)\\) is a SIG and not every induced subgraph of a SIG (CSIG) is a SIG (or CSIG). It is conjectured that the smallest \\(K_ n\\) which is not a SIG (CSIG) is \\(K_ 9\\). It is also proved that every tree on \\(n\\) vertices is an induced subgraph of a SIG, isomorphic to \\(G(S)\\) for some \\(S\\) with at most \\(2n-3\\) points.   Possibility of generalization to other metrics and higher dimensions is suggested.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310234$16F785E2-AA7E-49E9-A2F4-948B3B10FE50","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310234$1344CFFC-AF3F-403D-95A7-88240DBF6D12","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c82c987fd7300da6350c45c4c8c3df513b1cfa7","datavalue":{"value":"475043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310234$1D86C3BC-0245-4F49-9857-8630235F2374","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"382ec3a8d0aed862ec5747e982038215fb9894ca","datavalue":{"value":"sphere-of-influence graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310234$597C9B88-CA8D-42FA-A962-C5C82BD296D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310234$4AFC2FFE-1E55-4B2A-BDB6-B010609D4217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310234$B4991D87-6790-4EC5-A711-C62E7E768171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310234$FC6E3F70-348F-4355-8530-83A8DE1CE6CB","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":"Q1310234$73707849-5392-4C1A-970A-71F05D873EB1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee33f592c51a75e4c489985a8ba18707c6ff9bd7","datavalue":{"value":{"entity-type":"item","numeric-id":3685231,"id":"Q3685231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$7AED9F8F-45C3-49F6-80B8-F887BEFC9213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15651ff3707066357b2d3be59a6ba867a3e8959b","datavalue":{"value":{"entity-type":"item","numeric-id":5629250,"id":"Q5629250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$123F7D85-5CB0-46AE-9930-6875C6A899EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$CC398656-1534-4B69-8839-C464A21D3CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbcd06a03ffdfab095770a6004c5670b11186ed","datavalue":{"value":{"entity-type":"item","numeric-id":3692390,"id":"Q3692390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$DEF526D4-67E6-40BB-9086-DEF92DAABA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90c10f3313dde19a9252305df9d45bc029891d9e","datavalue":{"value":{"entity-type":"item","numeric-id":3049855,"id":"Q3049855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310234$4E28210D-EA06-4AF7-A127-4C8093C5AD3C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1073f850dc1edb372f80531c425db1556876f55a","datavalue":{"value":"https://doi.org/10.1016/0895-7177(93)90257-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1310234$B4289CF7-40AE-4226-89D7-76FECDF53B2C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ada2fe3dd6c0c42e4387f933651b93a698ab607d","datavalue":{"value":"W2059334547","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310234$55D1BC46-97E4-4AE7-9349-B69774B0CEB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cec3d969818ff4476fc47610eb0d12c86ce1c7b0","datavalue":{"value":{"entity-type":"item","numeric-id":4328185,"id":"Q4328185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30abd7388ae2a09f4499a0f392033fb3596f4e65","datavalue":{"value":{"amount":"+0.9439652","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$B0A6E30B-B7A2-4CA7-A30B-0401C0E01BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc5902f2197f45aef3df38878b602e2c56240a04","datavalue":{"value":{"entity-type":"item","numeric-id":4862245,"id":"Q4862245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2538d33744a9ea2fcb5f7dea13c64724009ffc2","datavalue":{"value":{"amount":"+0.9422888","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$F1EC06A3-79E8-4420-B035-031CBF3EE3AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"892fd14b954f3610944ee7f1ca14a99c363a2a73","datavalue":{"value":{"entity-type":"item","numeric-id":1596920,"id":"Q1596920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e3aa0de1e931d236247d8eb977eeeb047142bb","datavalue":{"value":{"amount":"+0.92165405","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$A0F1BB98-6C4A-4CF2-B17B-4C0CECA07854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4bb68997de044e79b068922f6c84a6f2d3f69aa","datavalue":{"value":{"entity-type":"item","numeric-id":3692390,"id":"Q3692390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6fa71eb051a384c3c09183f25abd481c3f666ca","datavalue":{"value":{"amount":"+0.91909575","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$BFF17620-5A96-4C4F-8CC8-F59476C501CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f8a35e682db6a1f80fcd10a982b7ff1b9613839","datavalue":{"value":{"entity-type":"item","numeric-id":1740485,"id":"Q1740485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95054bc2e7e48582d3ac63e334ca6e3be0822bcc","datavalue":{"value":{"amount":"+0.9157566","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$37E0063F-0F11-4C07-A48A-80E15CA8BA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aceefa5f0cbb3e4a9a07989a8c0cf7be71c18360","datavalue":{"value":{"entity-type":"item","numeric-id":5475528,"id":"Q5475528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb4e67f2e613b84a9765ec2f62b63ccbe91c19dd","datavalue":{"value":{"amount":"+0.9087452","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$91516ECA-83B4-4C7E-AF3A-86E39904CD32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5eb1af7fbb5c0316f13aceeb8ecb18781185a79f","datavalue":{"value":{"entity-type":"item","numeric-id":1339834,"id":"Q1339834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f58fba5e19db61001857c223639c469e32bae79","datavalue":{"value":{"amount":"+0.9014621","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$B50D65A3-3D7A-42CA-B6B9-F782449CF8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c91b8088fb8ec3d864fc2499bb043721647792ee","datavalue":{"value":{"entity-type":"item","numeric-id":5927945,"id":"Q5927945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d4215b6ab974a3c2f8f0b720aacb45fe5b37910","datavalue":{"value":{"amount":"+0.9004803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$C52C11A1-AEF0-4752-AD19-9303A1992609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a76bda2288ee17ccf43d93934c542b7e632e0feb","datavalue":{"value":{"entity-type":"item","numeric-id":5688089,"id":"Q5688089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49bc3e3a1476dba3907f3bda848a9b3938c366e5","datavalue":{"value":{"amount":"+0.8940858","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$B6A46B8F-41E0-4D6A-9AC9-7D8FC402ADCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1705fcca8ce613fbeb4ab7733deb79b129c1151","datavalue":{"value":{"entity-type":"item","numeric-id":1811067,"id":"Q1811067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2667483d95dfc72595bf0e86fa7ec5b7dee71617","datavalue":{"value":{"amount":"+0.88916963","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1310234$E1F16FEA-AEDC-405F-8987-85D03E8E9CD2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Abstract sphere-of-influence graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Abstract_sphere-of-influence_graphs"}}}}}