{"entities":{"Q686175":{"pageid":688024,"ns":120,"title":"Item:Q686175","lastrevid":63469617,"modified":"2026-04-11T13:22:50Z","type":"item","id":"Q686175","labels":{"en":{"language":"en","value":"A polynomial time circle packing algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428013"}},"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":"Q686175$B14ECB5E-A38A-4198-A71E-2F0FD1257CDE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f27731445f0a93b5298b018ad266b576f5d7a4e4","datavalue":{"value":{"text":"A polynomial time circle packing algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686175$CFF29F79-FBEC-4940-99CB-D14D4AAF0700","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"753125bdcfd3c1ce8b0c467aeb396c98052b063b","datavalue":{"value":"0785.52006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$53672A69-F5C3-470C-8D88-0B7D7A2E7658","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0edebb4cac24a0c1b01d5316ff357abaabc952d3","datavalue":{"value":"10.1016/0012-365X(93)90340-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$C32F6A3F-3A17-482D-ACBE-0BBDF2AD8553","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$C2ED10B1-C7B9-46D5-870F-62A4D787C4D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$07E5EC88-10CB-471F-82E3-81AC99F8EEFA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8440ff2952159be3ec3f246e7487a8ebdf82c379","datavalue":{"value":{"time":"+1994-04-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686175$AD70DCAC-B8F5-4A18-8B88-26A18B85603A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"087af6d0500960aedbc1b336b1df81d564fbbd61","datavalue":{"value":"A map on a surface \\(S\\) is a pair \\((G,S)\\) with \\(G\\) a graph which is 2-cell embedded in \\(S\\). A circle packing is a set of geodesic circles, with disjoint interiors, in a Riemannian surface \\(S'\\) of constant curvature. Connecting the midpoints of the circles with the touching points (with other circles or the same circle), one gets a graph on \\(S'\\). If such a graph is a map, isomorphic to the map \\(M=(G,S)\\), then one has a circle packing representation of \\(M\\). Simultaneous distinct circle packing representations of a map and its dual map, with any two dual edges crossing each other at the right angle in the corresponding circle touching point, are called primal-dual circle packing representations. A theorem of Koebe, Andreev, and Thurston says that if \\(M\\) is a triangulation then it admits a circle packing representation. The present paper contains extensions and improvements. The necessary and sufficient condition for a map to have a primal-dual circle packing representation is that its universal cover graph is 3-connected. Given a map \\(M\\) and a rational \\(\\varepsilon>0\\), then one can find an \\(\\varepsilon\\)- approximation for the primal-dual circle packing representation of \\(M\\) in polynomial time. In particular, there is a polynomial time algorithm producing simultaneous geodesic line convex drawings of a given map and its dual in a surface of constant curvature, so that only edges dual to each other cross.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686175$1D1C63F5-11FB-4584-AE20-B09182C3CD57","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a5031b3263da14f5abd118bd5a83bd1e3dacaeb4","datavalue":{"value":{"entity-type":"item","numeric-id":329396,"id":"Q329396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$988CCF2E-9A79-4537-A2A8-21062E2C022A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d37df3eeaabc93671e85ccca30b22399444c5039","datavalue":{"value":"52C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$7946D786-1CE3-43CD-A1D2-479DF18A1A69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$A240097E-D28E-4871-87A1-383932835AAC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"598b5024349ebc30afe33f7aaa464deaaaad9c72","datavalue":{"value":"428013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$89DB1FFA-83D1-4A84-A6D3-2A1E97210F9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0061d444635dc200bdb029d136d17f52aa90a9e","datavalue":{"value":"dual graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q686175$4A063B42-0CEE-44D9-B44B-496335938289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q686175$3C5B80CA-5C7C-4811-9024-5D6E89CD4385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q686175$1BB8FF1F-AD76-48B0-8AE3-35CCA0656A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a61078c375f595537fe4ec5567a249b4963887ff","datavalue":{"value":"geodesics","type":"string"},"datatype":"string"},"type":"statement","id":"Q686175$96DE99B4-561B-47FF-AAC3-13EEDB0ACB55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab9fd531eb49e245ff5d1ca3c7a778138e886649","datavalue":{"value":"circle packing representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q686175$549E531C-E702-4DE7-9FBB-6391558E7F0C","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":"Q686175$AFC6C1F4-F0A3-46AA-AF4C-88B83797B466","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"40b0322c4e2f2fba198fae73d0a70f8edd71a892","datavalue":{"value":{"entity-type":"item","numeric-id":5621735,"id":"Q5621735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$CC2C4F64-F9AC-46D1-9805-AC4C2A4F95FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de381c4a8b40f21efd98bc300e176ac833b87260","datavalue":{"value":{"entity-type":"item","numeric-id":5665849,"id":"Q5665849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$FD675F7C-0EE5-4479-9EA1-599976BF7466","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9d616c039dc5ba986006043b4d8aaa8f501495","datavalue":{"value":{"entity-type":"item","numeric-id":4735720,"id":"Q4735720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$A8455CFE-7B0B-4E2D-A845-1DAC88A468A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bfa60912437591e54fa940baf654ab71c9fd8dd","datavalue":{"value":{"entity-type":"item","numeric-id":1176645,"id":"Q1176645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$3E45A486-C207-40C7-BA38-6FCBA936EDB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd0ea59c3e83362763a1af6b4ffe39724e3fb97","datavalue":{"value":{"entity-type":"item","numeric-id":5767542,"id":"Q5767542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$B223862D-A7CA-423D-A9D2-3016EB1206F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4401fa0bdf2f04227d721ebf4584956e561c059","datavalue":{"value":{"entity-type":"item","numeric-id":3979445,"id":"Q3979445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$925D825D-9D55-4CBC-BF67-8DE499C1FD78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2045fc2ff8eca1ca2de634cc5326b053a1e46920","datavalue":{"value":{"entity-type":"item","numeric-id":3942069,"id":"Q3942069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$125FBC3B-33A3-4875-A96F-4AB63850BE8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d990a995876f36f7ec1a091c259d6d4e2b928d58","datavalue":{"value":{"entity-type":"item","numeric-id":5724435,"id":"Q5724435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686175$2724B4ED-9554-487B-9B64-EF6A69FE2467","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e79f846f7903e5f07947312c799582d27109c211","datavalue":{"value":"Q125757310","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$5BB7D610-4AB3-4345-8970-DCAE0FAA93F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e3ace7073256b9e8fa3cf5dee389012dcd6ee23","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90340-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q686175$2B993CD7-FD35-4D6D-8B8F-0D55A28F0D94","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"065bde0cc14393c47d80bd4a8afa692064cd076b","datavalue":{"value":"W2057382776","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686175$D04395BC-D34D-4F06-B3C9-694E43E80BE3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49501ffb28cb58d3d89f5536c539bbd6e32d6537","datavalue":{"value":{"entity-type":"item","numeric-id":1372615,"id":"Q1372615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c57a604f9d199a4a7c6869f020156e88687e8b30","datavalue":{"value":{"amount":"+0.9453970193862916","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":"Q686175$99F48373-7AD8-4BC5-A092-5444724A4D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c7c054a451fb13401819df9c7f5adb1245ebcea","datavalue":{"value":{"entity-type":"item","numeric-id":1182824,"id":"Q1182824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c57a604f9d199a4a7c6869f020156e88687e8b30","datavalue":{"value":{"amount":"+0.9453970193862916","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":"Q686175$FD33F0AC-8846-4536-B3DE-50B7188BC77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf92dad30ed7cf4e87f948db0702dca6ee635271","datavalue":{"value":{"entity-type":"item","numeric-id":4799228,"id":"Q4799228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e56c25a5e0394e0c9f5e8821e459f77ee34dfbf6","datavalue":{"value":{"amount":"+0.9060217142105104","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":"Q686175$41C37F54-CA56-4291-A09C-A6251DC18CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b81905490325987070c11adacb1365dbd69851af","datavalue":{"value":{"entity-type":"item","numeric-id":1176645,"id":"Q1176645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2e55bd7972e2c2210cc23874ec7b95a87b24077","datavalue":{"value":{"amount":"+0.7887399792671204","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":"Q686175$BE4C2E51-55A0-464C-B2DB-65AC7E208A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9196d922117270029105916efee5649afb5cd2b3","datavalue":{"value":{"entity-type":"item","numeric-id":1873691,"id":"Q1873691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e46de84f10233d6de055370c1add3bbf57f05585","datavalue":{"value":{"amount":"+0.7845759987831116","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":"Q686175$9F271713-FBC7-4CB0-B001-AD26379EE56D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial time circle packing algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_time_circle_packing_algorithm"}}}}}