English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It was noted already in the 90s that many classic graph classes, such asinterval, chordal, and bipartite graphs, can be characterized by the existenceof an ordering of the vertices avoiding some ordered subgraphs, calledpatterns. Very recently, all the classes corresponding to patterns on threevertices (including the ones mentioned above) have been listed, and proved tobe efficiently recognizable. In contrast, very little is known about patternson four vertices.  One of the few graph classes characterized by a pattern on four vertices isthe class of intersection graphs of rectangles that are said to be grounded ona line. This class appears naturally in the study of intersection graphs, andsimilar grounded classes have recently attracted a lot of attention.  This paper contains three parts. First, we make a survey of groundedintersection graph classes, summarizing all the known inclusions between thesevarious classes. Second, we show that the correspondence between a pattern onfour vertices and grounded rectangle graphs is not an isolated phenomenon. Weestablish several other pattern characterizations for geometric classes, andshow that the hierarchy of grounded intersection graph classes is tightlyinterleaved with the classes defined patterns on four vertices. We claim thatforbidden patterns are a useful tool to classify grounded intersection graphs.Finally, we give an overview of the complexity of the recognition of classesdefined by forbidden patterns on four vertices and list several interestingopen problems.

Classifying grounded intersection graphs via ordered forbidden patterns