Arrow Research search

Author name cluster

Stefan Felsner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers
2 author rows

Possible papers

10

MFCS Conference 2021 Conference Paper

Reconfiguring Independent Sets on Interval Graphs

  • Marcin Brianski
  • Stefan Felsner
  • Jedrzej Hodor
  • Piotr Micek

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size k are reconfigurable in an n-vertex interval graph, then there is a reconfiguration sequence of length 𝒪(k⋅ n²). We also provide a construction in which the shortest reconfiguration sequence is of length Ω(k²⋅ n). As a counterpart to these results, we also establish that Independent Set Reconfiguration is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

Details

MFCS Conference 2013 Conference Paper

On the Recognition of Four-Directional Orthogonal Ray Graphs

  • Stefan Felsner
  • George B. Mertzios
  • Irina Mustata

Abstract Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i. e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a 4 -directional orthogonal ray graph (4-DORG). Otherwise, if all rays are only pointing into the positive x and y directions, the intersection graph is a 2-DORG. Similarly, for 3-DORGs, the horizontal rays can have any direction but the vertical ones can only have the positive direction. The recognition problem of 2-DORGs, which are a nice subclass of bipartite comparability graphs, is known to be polynomial, while the recognition problems for 3-DORGs and 4-DORGs are open. Recently it has been shown that the recognition of unit grid intersection graphs, a superclass of 4-DORGs, is NP-complete. In this paper we prove that the recognition problem of 4-DORGs is polynomial, given a partition { L, R, U, D } of the vertices of G (which corresponds to the four possible ray directions). For the proof, given the graph G, we first construct two cliques G 1, G 2 with both directed and undirected edges. Then we successively augment these two graphs, constructing eventually a graph \(\widetilde{G}\) with both directed and undirected edges, such that G has a 4-DORG representation if and only if \(\widetilde{G}\) has a transitive orientation respecting its directed edges. As a crucial tool for our analysis we introduce the notion of an S-orientation of a graph, which extends the notion of a transitive orientation. We expect that our proof ideas will be useful also in other situations. Using an independent approach we show that, given a permutation π of the vertices of U ( π is the order of y -coordinates of ray endpoints for U ), while the partition { L, R } of V ∖ U is not given, we can still efficiently check whether G has a 3-DORG representation.

Details