{"entities":{"Q913833":{"pageid":915681,"ns":120,"title":"Item:Q913833","lastrevid":65310084,"modified":"2026-04-12T01:43:04Z","type":"item","id":"Q913833","labels":{"en":{"language":"en","value":"Ordered sets, pagenumbers and planarity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4148156"}},"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":"Q913833$201F68B3-4C3B-4D77-956B-2F1CE423186D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60a9029c0c5b3eacf42fc3391aac1078f58deb92","datavalue":{"value":{"text":"Ordered sets, pagenumbers and planarity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q913833$EA5C57E0-5B11-4D63-B337-C859C1366126","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"da756847812f9eb6fe800e143295f55c8bdbd323","datavalue":{"value":"0701.06005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$1DF6C619-EC56-4704-8687-A69F03F12A88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19573da0087f7b2837d1d04006a6937149373329","datavalue":{"value":"10.1007/BF00563521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$5ED20A01-BA73-49F7-8BA0-F06635992E53","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf71477dee8c3d88a058fccee959f7305df5ae47","datavalue":{"value":{"entity-type":"item","numeric-id":913832,"id":"Q913832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$C33F6D14-7676-4C17-BF9F-7C5D0C13D37F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5676fa5282611dbd0fab8edb7a4f82cf8ae7a025","datavalue":{"value":{"entity-type":"item","numeric-id":215016,"id":"Q215016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$73D9F223-DFA0-4A31-B130-FAFB94C29489","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$76B3E9AA-7D86-4A61-BD46-93DBA342C532","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q913833$E87B0E94-D2DA-4D0E-9A2A-CA514A7F2F7A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"33870d667f066a9c13c74a35cbae880adc951fc2","datavalue":{"value":"Given a digraph G, a book embedding is an embedding of the vertices and edges of G, with the vertices embedded along the spine (i.e., in a line fashion) and the edges on the pages so that each edge lies on only one page and so that no edges cross. The page number of G is the minimum number of pages needed for any book embeddng of G. If P is a poset, then P has associated graphs, e.g., the covering graph, the Hasse diagram, the relation graph with directed edge for each inequality \\(x<y\\). Each such graph has a page number. If G is the relation graph of P, we write \\(p(P,\\leq)\\) for \\(p(G)\\). Similarly \\(p(cov(P))\\) denotes the page number of the covering graph. Obviously, \\(p(cov(P))\\leq p(P,\\leq)\\), but the full relationship between these two invariants is not clear. The main and interesting theorem (T2) in this paper is the graph theoretical result that if cov(P) is a planar graph, i.e., if P is a planar poset, then \\(e(P)\\leq 2v(P)-2-2ht(P)\\), where e(P) is the number of edges, v(P) is the number of vertices and ht(P) is the height of \\(cov(P)\\) or P. From this theorem other bounds on \\(p(cov(P))\\) are derived. Using an argument on convex cutsets of P (or \\(cov(P))\\), some upper bounds are also obtained. These are used to determine that \\(p(\\underline k^ n)\\leq 2n-2\\) (T7), where \\(\\underline k\\) is an ordered chain with k vertices. From the point of view of scheduling, the page number is an interesting invariant if each edge represents a task to be performed and if pages represent subschedules of a particularly nice kind. The authors give some indication of this fact in their discussion and introduction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$806FEBC3-F5E9-47D8-A5D5-55BB23F35119","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$BCDA3B51-D807-4AEE-9490-DEBE5F113650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$6EED3F30-44E8-436B-A11B-DB09723864FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$5407D79D-FFFD-431E-BF88-6930686D0CA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"891939ef37f6c7e1e9454c2597f2e1ecd2a7fefe","datavalue":{"value":"4148156","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$078A56D1-F2F7-4ECB-BDCA-8D0B12A06063","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f766b5a4e14413c4d5468b9ceeee1004377e20a0","datavalue":{"value":"book number","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$5AFDD434-F58D-4E53-9135-320EAC36E819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c856145ef6cf7ef96d1f0755055e2ec6f5396f57","datavalue":{"value":"planarity","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$17E5B2D5-00F4-4AB1-BB29-E831718C73D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"311b860a0597dd249b584149fd2ab2e7e5bfa5ec","datavalue":{"value":"linear extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$1B7C5460-3BDA-46F2-A318-E7733CC97F84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e9b546562afba9bfeebc045b4015b20a62d228a","datavalue":{"value":"linear layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$3CA75D55-E629-4615-B5C2-955106B3A2BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"24198b416556221c891927e28dc5bda70bfeb4d9","datavalue":{"value":"book embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$5B0B25D2-38C5-4235-9418-BB901464E8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"611e3b9b76cececb73aa5503fbf01afa8e00714f","datavalue":{"value":"page number","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$705213AA-E371-4047-9635-17F487F8A298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dd8f6863138771bbebc289bdc9ec5e11396e78a","datavalue":{"value":"covering graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$3D1C222B-6C79-475F-9BB5-A61CEDECC4B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81973e3fdffb8f7dacb3816b946253b9196f6b4","datavalue":{"value":"Hasse diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$CAC6AF07-F519-4663-8D4B-112248231521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a5590cf44cd48f4bbdbce33d47e57eb3cf247be","datavalue":{"value":"relation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$C604AB45-E0F0-4867-8B79-20284BB62323","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$90A5DBE3-62C8-402A-B761-B2D2A9D82A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8a1a643f876753387126f6cfa27ba60d4ed86d1","datavalue":{"value":"planar poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$467DDE50-490A-4375-A465-9338AAFBC187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q913833$228CC6A3-626F-47E3-8E9F-61F84F7D6EC8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$BF4B1CC7-9889-4A13-9D47-4EF8DA4B26BD","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":"Q913833$AC6701AB-E554-4536-B73C-4B8897E4EC23","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bf0286d6b735487227d24437e14202203ff14c8","datavalue":{"value":{"entity-type":"item","numeric-id":3050437,"id":"Q3050437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$29B43A0D-14FF-478B-B518-1F640A7A80A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2860b21ec28091243d6f8b5601ce1d563a55934","datavalue":{"value":{"entity-type":"item","numeric-id":1136775,"id":"Q1136775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$E577A359-C179-4A8F-A1E1-290469CEC5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c4b125e8de8a7bb82b695f7f34e9b067a9ecafe","datavalue":{"value":{"entity-type":"item","numeric-id":3956998,"id":"Q3956998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$5B0AFD8C-B301-4B07-8EB7-4EFB88552C43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b602d01a898344ce4e168ea2188a5d94cd04e17","datavalue":{"value":{"entity-type":"item","numeric-id":4727445,"id":"Q4727445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$30119ED0-7312-453B-8ED2-272B795CC7DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00e2c96126d96cdefd036cb1bf73321d28cd54ba","datavalue":{"value":{"entity-type":"item","numeric-id":3764190,"id":"Q3764190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$4E0F1BFA-D64E-452A-A11F-833B5E8F264F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ab650a1770981f7d3ba01faa7c92ab3cccca1ae","datavalue":{"value":{"entity-type":"item","numeric-id":4071281,"id":"Q4071281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$AEEE6D93-6524-4356-8EAE-2F9AE924CA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eec97636d4258835391da95a5964d75c1c4d637","datavalue":{"value":{"entity-type":"item","numeric-id":913833,"id":"Q913833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q913833$BF2655D3-170B-491A-AE56-119A57DAA27F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"571837fbe53393f3db6c9bf87dae528c2d180d7b","datavalue":{"value":"https://doi.org/10.1007/bf00563521","type":"string"},"datatype":"url"},"type":"statement","id":"Q913833$A91DC523-E41E-4F2E-AA5D-93B302AFD2AE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b172030194f55a9fdf6b21363e14248bc08d5fc7","datavalue":{"value":"W2068287758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q913833$BBF38521-98B4-474F-A2D1-4905DB8856D8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b797cc82ef86c700efe4819de0a058280a3c694","datavalue":{"value":{"entity-type":"item","numeric-id":4201581,"id":"Q4201581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99dfe209b7a831c828670cb8415491634c6755a1","datavalue":{"value":{"amount":"+0.909689486026764","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":"Q913833$547ABB66-F228-4CDF-A41A-E35512E16C06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85b545c32f12fe32bda98c377dbcb3b36c947a15","datavalue":{"value":{"entity-type":"item","numeric-id":4377447,"id":"Q4377447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9793f56ac97a02481fdc07efd0b42daae559cc50","datavalue":{"value":{"amount":"+0.9057685136795044","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":"Q913833$CAF255E4-A062-4B7F-B74A-B0F1976F0855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da0774f0c116e9b7bc75310982df6f38ef3310e0","datavalue":{"value":{"entity-type":"item","numeric-id":2804780,"id":"Q2804780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77c9d8dfceb5c1ec2c6dbae1d473fc9a85e472c6","datavalue":{"value":{"amount":"+0.8558135032653809","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":"Q913833$B3CE3E53-896D-4EF6-91E2-86101196F3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e831eedf0d16635a5c408abb9201d9730a80a72f","datavalue":{"value":{"entity-type":"item","numeric-id":4694751,"id":"Q4694751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"672151a0f2dfe39472402bd8dbdba79d80d5deb0","datavalue":{"value":{"amount":"+0.8278953433036804","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":"Q913833$10B3D6AF-5A89-4689-9645-272593B729D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c39fd2579b81dc5018c7a1b94d9299f6521c0038","datavalue":{"value":{"entity-type":"item","numeric-id":1121926,"id":"Q1121926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"672151a0f2dfe39472402bd8dbdba79d80d5deb0","datavalue":{"value":{"amount":"+0.8278953433036804","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":"Q913833$9A86582E-E44C-4F14-8C92-79E487CEE9AB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Ordered sets, pagenumbers and planarity","badges":[]}}}}}