13 citations · 24 across the 6 of their papers we have counts for
8 papers
Recognising the overlap graphs of subtrees of restricted trees is hard
Jessica Enright, Martin Pergel
The overlap graphs of subtrees in a tree (SOGs) generalise many other graphs classes with set representation characterisations. The complexity of recognising SOGs in open. The comp…
What Makes the Recognition Problem Hard for Classes Related to Segment and String graphs?
Irina Mustata, Martin Pergel
We explore what could make recognition of particular intersection-defined classes hard. We focus mainly on unit grid intersection graphs (UGIGs), i.e., intersection graphs of unit-…
On flips in planar matchings
Marcel Milich, Torsten Mütze, Martin Pergel
In this paper we investigate the structure of flip graphs on non-crossing perfect matchings in the plane. Specifically, consider all non-crossing straight-line perfect matchings on…
On edge intersection graphs of paths with 2 bends
Martin Pergel, Paweł Rzążewski
An EPG-representation of a graph is a collection of paths in a plane square grid, each corresponding to a single vertex of , so that two vertices are adjacent if and only if…
A Note on Graphs with 2 Bends
Martin Pergel
We show NP-completeness for the recognition problem of 2-line-bend graphs.
The Complexity of the Partial Order Dimension Problem - Closing the Gap
Stefan Felsner, Irina Mustata, Martin Pergel
The dimension of a partial order is the minimum number of linear orders whose intersection is . There are efficient algorithms to test if a partial order has dimension at mo…