Parameters of Bar k-Visibility Graphs (2009)
Stefan Felsner, Mareike Massow
www.math.tu-berlin.de/diskremath
Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets (2009)
Felsner, Stefan, Massow, Mareike
The linear extension diameter of a finite poset P is the maximum distance between a pair of linear extensions of P, where the distance between two linear extensions is the number of pairs of elements...
On the Order Dimension of Outerplanar Maps (2009)
Felsner, Stefan, Nilsson, Johan
Schnyder characterized planar graphs in terms of order dimension. Brightwell and Trotter proved that the dimension of the vertex-edge-face poset $\Pvef{M}$ of a planar map $M$ is at most four. In...
Von Fakultät, Ii Mathematik Naturwissenschaften, Vorsitzender Prof, Dr. Michael Scheutzow, Berichter Prof, ...
First of all I want to thank my advisor, Stefan Felsner. In lectures and many discussions I learned a lot from him not only about graph theory and combinatorics. He was also willing to share the...
Intersection Graphs of Pseudosegments: Chordal Graphs (2008)
Dangelmayr, Cornelia, Felsner, Stefan, Trotter, William T.
We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. For positive we have a construction which shows that all chordal graphs that can be represented as...
Binary labelings for bipartite graphs ∗ (2008)
Stefan Felsner, Clemens Huemer, David Orden
Part of the authors introduced in [C. Huemer, S. Kappes, A binary labelling for plane Laman graphs and quadrangulations, in Proceedings of the 22nd European Workshop on Computational Geometry...
On the Number of α-Orientations (2008)
Stefan Felsner, Florian Zickfeld
We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice...
Orthogonal Surfaces and their CP-orders (2008)
Abstract. Orthogonal surfaces are nice mathematical objects which have interesting connections to various fields, e.g., integer programming, monomial ideals and order dimension. While orthogonal...
Topic: Schnyder Woods and Geometric Representations of Graphs (2008)
Name Florian Zickfeld, Stefan Felsner
In the last six months I have mainly worked on problems from two different areas. I will first give an overview of my work on the number of orientations with fixed out-degrees. In contrast to this...
Ideas for a Thesis Project: Drawing Partial Orders (2008)
Mareike Massow, Advisor Prof, Dr. Stefan Felsner
Suppose we are given a partially ordered set P = (X, <) and aim to draw it in the plane. How can we find a good way of doing this? First of all: What makes a drawing good? One possible answer to...
Bijections for Baxter Families and Related Objects (2008)
Felsner, Stefan, Fusy, Éric, Noy, Marc, Orden, David
The Baxter number can be written as $B_n = \sum_0^n \Theta_{k,n-k-1}$. These numbers have first appeared in the enumeration of so-called Baxter permutations; $B_n$ is the number of Baxter...
Dimension, graph and hypergraph coloring (2007)
Abstract. There is a natural way to associate with a poset P a hypergraph HP, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of HP. The ordinary graph...
Abstract. Given a simple arrangement of n pseudolines in the Euclidean plane, associate with line i the list oe i of the lines crossing i in the order of the crossings on line i. oe i = (oe i
Stefan Felsner, Jens Gustedt, Michel Morvan
Abstract. We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P. Two bijections of this type have...
Stefan Felsner, Ludmila Scharf
2 Problem.............................. 4 2.1 Model for the problem.................. 4
Hamiltonicity and Colorings of Arrangement Graphs (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical)...
Hamiltonicity and Colorings of Geometric Graphs (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (aÆne or projective) and pseudocircle (spherical)...
Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number (2007)
Stefan Felsner, Vijay Raghavan, Jeremy Spinrad
. Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be...
Markov Chains for Linear Extensions, (2007)
Stefan Felsner, Lorenz Wernisch
Abstract. We study the generation of uniformly distributed linear extensions using Markov chains. In particular we show that monotone coupling from the past can be applied in the case of linear...
Stefan Felsner, Stephen Wismath
Abstract. This paper investigates the following question: Given an integer grid , where is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
Point-sets with few k-sets Helmut Alt (2007)
Stefan Felsner, Ferran Hurtado, Marc Noy, Emo Welzl
A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is...
Abstract. An oriented hyperplane is a hyperplane with designated good and bad sides. The infeasibility of a cell in an arrangement A of oriented hyperplanes is the number of hyperplanes with this...
Abstract. The distance between two permutations of the same set X is the number of pairs of elements being in different order in the two permutations. Given a poset P = (X;), a pair L 1; L 2 of...
Constructing Colorings for Diagrams (2007)
Stefan Felsner, Jens Gustedt, Michel Morvan, Jean-xavier Rampon
Introduction and Overview An undirected graph G = (V; E) is a (Hasse--) diagram if there is a poset P = (V; !) and an orientation ~ E of E such that (x; y) 2 ~ E iff x ! y in P and there is no z with...
Felsner, Stefan, Kloch, Kamil, Matecki, Grzegorz, Micek, Piotr
We analyze special cases of the on-line chain partition problem of up-growing orders. One result is a lower bound for 2-dimensional orders. Together with the old upper bound this yields the precise...
Chordal Graphs as Intersection Graphs of Pseudosegments (2007)
Dangelmayr, Cornelia, Felsner, Stefan
We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. The main contribution is a construction which shows that all chordal graphs which have a...
Thickness of Bar 1-Visibility Graphs (2007)
Massow, Mareike, Felsner, Stefan
Bar k-visibility graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight which can...
Schnyder Woods and Orthogonal Surfaces (2007)
Felsner, Stefan, Zickfeld, Florian
In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory....
Chordal Graphs as Intersection Graphs of Pseudosegments (2007)
Dangelmayr, Cornelia, Felsner, Stefan
We investigate which chordal graphs have a representation as intersection graphs of pseudosegments. The main contribution is a construction which shows that all chordal graphs which have a...
Thickness of Bar 1-Visibility Graphs (2007)
Massow, Mareike, Felsner, Stefan
Bar k-visibility graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight which can...
Schnyder Woods and Orthogonal Surfaces (2007)
Felsner, Stefan, Zickfeld, Florian
In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension theory....
Parameters of Bar k-Visibility Graphs (2007)
Stefan Felsner, Mareike Massow
Bar k-visibility graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight which can...
Thickness of bar 1-visibility graphs (2007)
Stefan Felsner, Mareike Massow
Abstract. Bar k-visibility graphs are graphs admitting a representation in which the vertices correspond to horizontal line segments, called bars, and the edges correspond to vertical lines of sight...
Binary Labelings for Plane Quadrangulations and their Relatives (2006)
Felsner, Stefan, Huemer, Clemens, Kappes, Sarah, Orden, David
Motivated by the bijection between Schnyder labelings of a plane triangulation and partitions of its inner edges into three trees, we look for binary labelings for quadrangulations (whose edges can...
Felsner, Stefan, Kappes, Sarah
Orthogonal surfaces are nice mathematical objects which have interesting connections to various fields, e.g., integer programming, monomial ideals and order dimension. While orthogonal surfaces in...
Empty Rectangles and Graph Dimension (2006)
We consider rectangle graphs whose edges are defined by pairs of points in diagonally opposite corners of empty axis-aligned rectangles. The maximum number of edges of such a graph on $n$ points is...
Schnyder woods and orthogonal surfaces (2006)
Stefan Felsner, Florian Zickfeld
Abstract. In this paper we study connections between Schnyder woods and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and dimension...
Schnyder woods and orthogonal surfaces (2006)
Stefan Felsner, Florian Zickfeld
In this paper we study connections between planar graphs, Schnyder woods, and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and the...
Empty Rectangles and Graph Dimension (2006)
Abstract We consider rectangle graphs whose edges are defined by pairs of points in diagonally opposite corners of empty axis-aligned rectangles. The maximum number of edges of such a graph on n...
Alcalá De Henares, M. J. Chávez, A. Quintero, M. T. Villar, Cornelia Dangelmayr, Stefan Felsner, ...
The structure of flag sphere triangulations
Grid orientations, (d, d + 2)-polytopes, and arrangements of pseudolines (2005)
Stefan Felsner, Bernd Gärtner, Falk Tschirschnitz
We investigate the combinatorial structure of linear programs on simple d-polytopes with d + 2 facets. These can be encoded by admissible grid orientations. Admissible grid orientations are also...
Weak Positional Games on Hypergraphs of Rank Three (2005)
In a weak positional game, two players, Maker and Breaker, alternately claim vertices of a hypergraph until either Maker wins by getting a complete edge or all vertices are taken without this...
Discrepancy of Products of Hypergraphs (2005)
Doerr, Benjamin, Hebbinghaus, Nils, Felsner, Stefan
For a hypergraph {${\mathcal{H} = (V,\mathcal{E})}$}, its {${d}$}--fold symmetric product is {${ \Delta ^{d} \mathcal{H} = (V^{d},\{ E^{d} | E {\in}\mathcal{E} \}) }$}. We give several upper and...
Deterministic Random Walks on the Integers (2005)
Cooper, Joshua, Doerr, Benjamin, Spencer, Joel, Tardos, Gabor, Felsner, Stefan
Convex Drawings of 3-Connected Plane Graphs (Extended Abstract) (2004)
Bonichon, Nicolas, Felsner, Stefan, Mosbah, Mohamed
We use Schnyder woods of 3-connected planar graphs to produce convex straight line drawings on a grid of size (n-2-\Delta) x (n-2-\Delta). The parameter \Delta >= 0 depends on the the Schnyder wood...
Convex Drawings of 3-Connected Plane Graphs (Extended Abstract) (2004)
Bonichon, Nicolas, Felsner, Stefan, Mosbah, Mohamed
We use Schnyder woods of 3-connected planar graphs to produce convex straight line drawings on a grid of size (n-2-\Delta) x (n-2-\Delta). The parameter \Delta >= 0 depends on the the Schnyder wood...
Convex Drawings of 3-Connected Plane Graphs (Extended Abstract) (2004)
Bonichon, Nicolas, Felsner, Stefan, Mosbah, Mohamed
We use Schnyder woods of 3-connected planar graphs to produce convex straight line drawings on a grid of size (n-2-\Delta) x (n-2-\Delta). The parameter \Delta >= 0 depends on the the Schnyder wood...
Lattice Structures from Planar Graphs (2004)
The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. This general theorem is proven in the first part of the paper. In the second...
Lattice Structures from Planar Graphs (2004)
The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. This general theorem is proven in the rst part of the paper. In the second...
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (2003)
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given a grid ,where is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at...
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen
This paper investigates the following question: Given an integer grid $\phi$, where $\phi$ is a proper subset of the integer plane or a proper subset of the integer 3d space, which graphs admit...
Straight-line drawings on restricted integer grids in two and three dimensions (2002)
S. Felsner, G. Liotta, S. K. Wismath, Stefan Felsner, Stephen Wismath
expository and student works, in addition to research documents. A work appearing in this report series may not have undergone any prior review, and so the Department cannot assume any liability...
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given an integer grid...
Geodesic Embeddings and Planar Graphs (2002)
Schnyder labelings are known to have close links to order dimension and drawings of planar graphs. It was observed by Ezra Miller that geodesic embeddings of planar graphs are another class of...
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (2002)
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given a grid , where is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at...
Lattice Structures from Planar Graphs (2002)
The set of all orientations of a planar graph with prescribed outdegrees carries the structure of a distributive lattice. This general theorem is proven in the rst part of the paper. In the second...
Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions (2002)
Stefan Felsner, Giuseppe Liotta, Stephen Wismath
This paper investigates the following question: Given a grid , where is a proper subset of the integer 2D or 3D grid, which graphs admit straight-line crossing-free drawings with vertices located at...
OTTO-VON-GUERICKE-UNIVERSITÄT MAGDEBURG (2002)
Liebe Kombinatorikerinnen, Stefan Felsner, Alexander Pott, Hauptvorträge G, Tagungsbüro G
ein herzliches Dankeschön. Wir versuchen, die Tradition dieser von Walter Deuber initiierten Veranstaltung weiterleben zu lassen, an zwei Tagen eine Mischung unterschiedlicher Aspekte der...
Sweeps, arrangements and signotopes (2001)
Abstract. Sweeping is an important algorithmic tool in geometry. In the rst part of this paper we dene sweeps of arrangements and use the `Sweeping Lemma ' to show that Euclidean arrangements of...
Sweeps, arrangements and signotopes (2001)
Abstract. Sweeping is an important algorithmic tool in geometry. In the first part of this paper we define sweeps of arrangements and use the `Sweeping Lemma ' to show that Euclidean...
Convex drawings of planar graphs and the order dimension of 3-polytopes (2001)
Abstract. We dene an analogue of Schnyder's tree decompositions for 3-connected planar graphs. Based on this structure we obtain: Let G be a 3-connected planar graph with f faces, then G has a...
Infeasibility of Systems of Halfspaces (2001)
An oriented hyperplane is a hyperplane with designated good and bad sides. The infeasibility of a cell in an arrangement A of oriented hyperplanes is the number of hyperplanes with this cell on the...
The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene (2000)
Stanley conjectured that the number of maximal chains in the weak Bruhat order of Sn, or equivalently the number of reduced decompositions of the reverse of the identity permutation w0 = n, n − 1,n...
The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene (2000)
Stanley conjectured that the number of maximal chains in the weak Bruhat order of S n, or equivalently the number of reduced decompositions of the reverse of the identity permutation w 0 = n; n...
Posets and planar graphs (2000)
Abstract. In 1989, W. Schnyder proved that a graph is planar if and only if its dimension is at most 3. Although dimension is an integer valued parameter, we introduce a fractional version of...
Hamiltonicity and colorings of arrangement graphs (2000)
Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (ane or projective) and pseudocircle (spherical)...
Hamiltonicity and Colorings of (2000)
Arrangement Graphs Stefan, Stefan Felsner, Ferran Hurtado, Marc Noy, Ileana Streinu
We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (ane or projective) and pseudocircle (spherical)...
Posets and planar graphs (2000)
Stefan Felsner, William T. Trotter
DOI 10.1002/jgt.20081 Abstract: Usually dimension should be an integer valued parameter. We introduce a refined version of dimension for graphs, which can assume a value t 1 l t Š, thought to be...
Triangles in Euclidean arrangements (1999)
Abstract. The number of triangles in arrangements of lines and pseudolines has been object of some research. Most results, however, concern arrangements in the projective plane. In this article we...
Maximum k-chains in planar point sets: Combinatorial structure and algorithms (1999)
Stefan Felsner, Lorenz Wernisch
Germany. A chain of a set P of n points in the plane is a chain of the dominance order on P. A k-chain is a subset C of P that can be covered by k chains. A k-chain C is a maximum k-chain if no other...
The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene (1999)
. Stanley conjectured that the number of maximal chains in the weak Bruhat order of Sn , or equivalently the number of reduced decompositions of the reverse of the identity permutation rev n = n; n...
Zonotopes Associated with Higher Bruhat Orders (1999)
Stefan Felsner, Günter M. Ziegler, Fachbereich Mathematik
The higher Bruhat orders B(n, k) are combinatorially defined partial orders (and hence graphs) that "look like" the graphs of (n k)-dimensional zonotopes -- and they are, for small...
On the Complexity of Partial Order Properties (1999)
Stefan Felsner, Ravi Kant, C. Pandu Rangan, Dorothea Wagner
The recognition complexity of ordered set properties is considered (in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property). We...
The Maximum Number of Edges in a Graph of Bounded Dimension, with Application to Ring Theory (1999)
Geir Agnarsson, Stefan Felsner, William T. Trotter
With a finite graph G = (V, E), we associate a partially ordered set P = (X, P) with X = V ∪ E and x < e in P if and only if x is an endpoint of e in G. This poset is called the incidence...
Stefan Felsner, William T. Trotter
Abstract. There is a natural way to associate with a poset P a hypergraph H P, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of H P. The ordinary...
Tolerance graphs and orders (1998)
We show that if a tolerance graph is the complement of a comparability graph it is a trapezoid graph, i.e., the complement of an order of interval dimension at most 2. As consequences we are able to...
Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices (1998)
Stefan Felsner, Stefan Felsner, Jens Gustedt, Jens Gustedt, Michel Morvan, Michel Morvan
. We discuss bijections that relate families of chains in lattices associated to an order P and families of interval orders defined on the ground set of P . Two bijections of this type have been...
A Theorem on Higher Bruhat Orders (1998)
Stefan Felsner, Helmut Weil, For X
We show that inclusion order and single-step inclusion coincide for higher Bruhat orders B(n; 2), i.e., B(n; 2) = B` (n; 2).
Finite Three Dimensional Partial Orders Which Are Not Sphere Orders (1998)
Stefan Felsner, Peter C. Fishburn, William T. Trotter
. Given a partially ordered set P = (X; P ), a function F which assigns to each x 2 X a set F (x) so that x y in P if and only if F (x) ` F (y) is called an inclusion representation. Every poset has...
Point-Sets With Few K-Sets (1998)
Helmut Alt, Stefan Felsner, Ferran Hurtado, Marc Noy
A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is...
Trapezoid graphs and generalizations, geometry and algorithms (1997)
Stefan Felsner, Rudolf M, Lorenz Wernisch
Trapezoid graphs are a class of cocomparability graphs containing interval graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic and Pinter [DGP]. They propose an O(n...
On-line chain partitions of orders (1997)
Abstract. We analyze the on-line chain partitioning problem as a two-person game. One person builds an order one point at a time. The other person responds by making an irrevocable assignment of the...
Trapezoid graphs and generalizations, geometry and algorithms (1997)
Stefan Felsner, Rudolf M Uller, Lorenz Wernisch
Trapezoid graphs are a class of cocomparability graphs containing interval graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic and Pinter [DGP]. They propose an O(n...
Finite Three Dimensional Partial Orders Which Are Not Sphere Orders (1997)
Stefan Felsner, Peter C. Fishburn, WILLIAM T. TROTTER
. Given a partially ordered set P = (X; P ), a function F which assigns to each x 2 X a set F (x) so that x y in P if and only if F (x) ` F (y) is called an inclusion representation. Every poset has...
Colorings of Diagrams of Interval Orders and α-Sequences of Sets (1995)
Stefan Felsner, William T. Trotter
. We show that a proper coloring of the diagram of an interval order I may require 1 + dlog 2 height(I) e colors and that 2 + dlog 2 height(I) e colors always suffice. For the proof of the upper...
On the fractional dimension of partially ordered sets (1994)
Stefan Felsner, William T. Trotter
Abstract. We use a variety of combinatorial techniques to prove several theorems concerning fractional dimension of partially ordered sets. In particular, we settle a conjecture of Brightwell and...
On the fractional dimension of partially ordered sets (1994)
Stefan Felsner, William T. Trotter
Abstract. We use a variety of combinatorial techniques to prove several theorems concerning fractional dimension of partially ordered sets. In particular, we settle a conjecture of Brightwell and...
Semi-order dimension two is a comparability invariant (1994)
Stefan Felsner, Rolf H. Mohring
Abstract. A partial order P = (X;!P) is a semi-order if it is an interval order admitting an interval representation such that all the intervals are of unit length. The semi-order dimension of P is...
Trapezoid Graphs and Generalizations, Geometry and Algorithms (1994)
Stefan Felsner, Rudolf Müller, Lorenz Wernisch
Trapezoid graphs are a class of cocomparability graphs containing interval graphs and permutation graphs as subclasses. They were introduced by Dagan, Golumbic and Pinter [DGP]. They propose an O(n 2...
On-Line Chain Partitions of Orders (1994)
We analyze the on-line chain partitioning problem as a two-person game. One person builds an order one point at a time. The other person responds by making an irrevocable assignment of the new point...
3-Interval Irreducible Partially Ordered Sets (1994)
. In this paper we discuss the characterization problem for posets of interval dimension at most 2. That is, we attempt to compile the minimal list of forbidden posets for interval dimension 2....
On the Complexity of Partial Order Properties (1993)
Stefan Felsner, Dorothea Wagner
The recognition complexity of ordered set properties is considered, i.e. how many questions have to be asked to decide if an unknown ordered set has a prescribed property. We prove a lower bound of...
Interval orders [microform] : combinatorial structure and algorithms / (1992)
Thesis (doctoral)--Technische Universität Berlin, 1992.
Bounds for the Jump Number of Partially Ordered Sets (1992)
this paper we will propose some strengthenings of the width bound. A different approach to bound s(P ) is due to Gierz, Poguntke [?] they proved rank(M P ) jP j \Gamma s(P ) \Gamma 1, where M P...
Bounds for the Jump Number of Partially Ordered Sets (1991)
A linear extension of a partial order P is a linear order L = x1, x2..., xn respecting the order relations of P, i.e. xi < xj implies i < j for all xi, xj ∈ P. In other words, L is the linear...
A 3/2–aproximation algorithm for the jump number of interval orders, Order 6 (1990)
The jump number of a partial order P is the minimum number of incomparable adjacent pairs in some linear extension of P. The jump number problem is known to be NP--hard in general. However some...
Bijections for Baxter Families and Related Objects
Stefan Felsner, Marc Noy, Departament Matemàtica, Aplicada Ii, Éric Fusy, ...
The Baxter number Bn can be written as Bn = � n 0 Θk,n−k−1 with Θk,ℓ = 2 (k + 1) 2 (k + 2)
Orthogonal Structures in Directed Graphs
this paper is to show how the concept of 1--weightings and the technique used by Frank can be used to obtain a similar theory for directed graphs. In the next section we develop the network flow...
Zonotopes Associated with Higher Bruhat Orders
Stefan Felsner, Günter M. Ziegler, Fachbereich Mathematik
The higher Bruhat orders B(n; k) are combinatorially defined partial orders (and hence graphs) that "look like" the graphs of (n k)-dimensional zonotopes -- and they are, for small...