{"entities":{"Q2277492":{"pageid":2288235,"ns":120,"title":"Item:Q2277492","lastrevid":59708241,"modified":"2026-04-10T13:39:19Z","type":"item","id":"Q2277492","labels":{"en":{"language":"en","value":"Characterization of the graphs with boxicity \\(\\leq 2\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4196019"}},"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":"Q2277492$B2034844-4C04-49DE-A741-DA468A398C2D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30569a4ff20447da5fa7d488adaef2d1e1215436","datavalue":{"value":{"text":"Characterization of the graphs with boxicity \\(\\leq 2\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277492$A909482A-C8FE-40EC-97DA-E125E2EF5EDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b8f2a4a719a629b7870ff5bb1764f60a57c243a7","datavalue":{"value":"0725.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277492$638B4470-F256-4169-B137-39D6F711B27F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7caed6a67ff2245616b11d8d02afe6eb3deeea98","datavalue":{"value":"10.1016/0012-365X(90)90151-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277492$E0E4086D-2F1F-4F7D-91D8-A12ECAB983E9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8b9ed079ad79b407d74ce54997c45f5e2eaa2a02","datavalue":{"value":{"entity-type":"item","numeric-id":2277491,"id":"Q2277491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$75C3160C-B76A-4CA7-BF6C-0D1CC55E0266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef275966fb7ffb4472927516071e53e229619fef","datavalue":{"value":{"entity-type":"item","numeric-id":703682,"id":"Q703682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$BEDA0C35-9BA3-4602-A808-A1F0880E4B6B","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":"Q2277492$5C370572-6AE8-42F2-85FF-3DC5CC461FE1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2277492$09F34630-99B9-4F63-84F4-2025B98A804E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a55ffa2fa624cb26d708880ec0d2752dcf199414","datavalue":{"value":"The boxicity of a graph G is the least dimension d such that G is isomorphic to the incidence graph of a set of d-dimensional boxes. Interval graphs are graphs with boxicity 1, and are characterised as admitting an incidence matrix of vertices with maximal cliques C(G) such that in each column (corresponding to some vertex) all 1's are consecutive. In this paper an analogous characterization of graphs of boxicity 2 is derived. This is obtained by constructing a series of matrices by replacing certain elements of C(G) with *. G is then of boxicity 2 iff in each of these matrices all 1's are consecutive in each column, disregarding the *'s.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277492$3918DC92-A7E4-434D-B0F7-29428AC8340D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$CE6BA581-6489-4A2B-9461-15637E07DC0E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277492$6862DAAB-F605-47C8-9B44-08DE9096C204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277492$E686DFC3-054F-44E9-B9A9-B72FD30B3AF3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f45be1afd0b1f85b4479ea3add15b2560ee5ce1","datavalue":{"value":"4196019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277492$6B83B433-8934-4DDC-A358-6D7AFDA4F0E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0019c63940125554689e346877910b261e79216","datavalue":{"value":"boxicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277492$2802E15B-29A7-404C-9826-9C10B4D52AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4e792ff646f6fa664efd2613027c94cc69a7563","datavalue":{"value":"incidence graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277492$C8708905-72B9-42C4-8D4A-C491A633B2AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"262bdfa8edfe99210fd9b6503f70cfab463acd03","datavalue":{"value":"incidence matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277492$B01CA4DB-7746-4485-B951-A4210E120D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277492$022FF6BF-17C8-4206-A41E-6F3EEDF43BA2","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":"Q2277492$AD0B01DB-04F2-4068-97E9-B86DC6E5CB70","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c74b7954c4e96ea2e676044196dc57d8b06146d","datavalue":{"value":{"entity-type":"item","numeric-id":2395457,"id":"Q2395457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$645C557D-2CC9-494A-ACA5-D09B5EEF4ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc1236a6b7e888ea271edc7a134a09ce07c03dec","datavalue":{"value":{"entity-type":"item","numeric-id":1060229,"id":"Q1060229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$88B90670-350F-4EAF-B582-9136770B0D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$1D6F2E2E-D035-4AED-B0A4-00690B85C12F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ea24d0d08bd225859187316389977dd9b54dcc","datavalue":{"value":{"entity-type":"item","numeric-id":5588433,"id":"Q5588433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277492$FFAD862D-3238-4F8E-A52B-89189E556E07","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"effc12ab36f025525b2459be1383ef2286cdedb4","datavalue":{"value":"https://doi.org/10.1016/0012-365x(90)90151-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q2277492$A8E18BBF-B464-4C45-BA86-0DD5FBB36680","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eae598ce01ace8a0a844503fc4b5a9b112dd25f7","datavalue":{"value":"W2009945076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277492$C5C28B90-BE8E-45AA-B259-822670D45899","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d8aaebdd12fd854e6512bea0a3042d05624f973","datavalue":{"value":{"entity-type":"item","numeric-id":685652,"id":"Q685652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0c9cfe81f30b01a175ec0c36fa88787525a2bcb","datavalue":{"value":{"amount":"+0.7853347063064575","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":"Q2277492$F1FA8442-E44B-4D4D-8518-73822634E408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1712b5115bc62efc944ee11fd33d9fbb9fd7f94a","datavalue":{"value":{"entity-type":"item","numeric-id":1024326,"id":"Q1024326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49cb6b986dd3cb4581d674e76091fae615d6f486","datavalue":{"value":{"amount":"+0.7766020894050598","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":"Q2277492$3F6943D2-3443-4F74-ABD9-B1EE4A55B0E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6fe4144f6f67dc1f484ff5ebc708e11d7a9a56a","datavalue":{"value":{"entity-type":"item","numeric-id":5174960,"id":"Q5174960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"934e2cf0bd7a8ddb9669b5987f0b3e514de1dbc2","datavalue":{"value":{"amount":"+0.7655516266822815","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":"Q2277492$1B0D73D0-9D80-48A4-B98B-98A9B75D4A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e82ae98982aeced7dab3cf36d3545ddf18db8f5","datavalue":{"value":{"entity-type":"item","numeric-id":2477634,"id":"Q2477634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39e04e4a7268a3be9f0a0cfe8466677da50073b6","datavalue":{"value":{"amount":"+0.7606120705604553","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":"Q2277492$062DAF09-6565-4A5E-A00A-C95E73599509","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277492","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277492"}}}}}