{"id":2550,"date":"2023-11-27T13:29:09","date_gmt":"2023-11-27T16:29:09","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=2550"},"modified":"2023-11-27T13:29:09","modified_gmt":"2023-11-27T16:29:09","slug":"intersection-models-and-forbidden-pattern-characterizations-for-2-thin-and-proper-2-thin-graphs","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/intersection-models-and-forbidden-pattern-characterizations-for-2-thin-and-proper-2-thin-graphs\/","title":{"rendered":"Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs"},"content":{"rendered":"

Authors: Flavia Bonomo-Braberman and Gast\u00f3n Abel Brito.<\/p>\n

Abstract:
\nThe thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Graphs with thinness at\u00a0most two include, for example, bipartite convex graphs. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable\u00a0representation of the graph. Proper thinness is defined analogously, generalizing proper interval graphs, and a larger family of NP-complete problems are known to be\u00a0polynomially solvable for graphs with bounded proper thinness.<\/p>\n

The complexity of recognizing 2-thin and proper 2-thin graphs is still open. In this work, we present characterizations of 2-thin and proper 2-thin graphs as\u00a0intersection graphs of rectangles in the plane, as vertex intersection graphs of paths on a grid (VPG graphs), and by forbidden ordered patterns. We also prove that\u00a0independent 2-thin graphs are exactly the interval bigraphs, and that proper independent 2-thin graphs are exactly the bipartite permutation graphs.<\/p>\n

Finally, we take a step towards placing the thinness and its variations in the landscape of width parameters, by upper bounding the proper thinness in terms of the\u00a0bandwidth.<\/p>\n

More Information:
\nhttps:\/\/www.sciencedirect.com\/science\/article\/abs\/pii\/S0166218X23002354<\/a><\/p>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":9,"featured_media":2551,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[98],"tags":[],"class_list":["post-2550","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-papers"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2550","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=2550"}],"version-history":[{"count":1,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2550\/revisions"}],"predecessor-version":[{"id":2552,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2550\/revisions\/2552"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/2551"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=2550"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=2550"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=2550"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}