Stefan Felsner's Publications

  1. A 3/2-Approximation Algorithm for the Jump Number of Interval Orders
    Order 6 (1990), 325-334. [pdf]

  2. Orthogonal Structures in Directed Graphs
    Journal of Combinatorial Theory (B) 57 (1993), 309-321. [pdf]

  3. More Bounds for the Dimension of Interval Orders
    with M. Morvan. [pdf]

  4. Bounds for the Jump Number of Partially Ordered Sets
    Methods of Operations Research 64 (1991), 117-121. [pdf]

  5. On the Interplay of Interval Dimension and Dimension
    with M. Habib and R.H. Möhring
    SIAM Journal of Discrete Mathematics 7 (1994), 32-40. [pdf]

  6. Constructing Colorings for Diagrams
    with J. Gustedt, M. Morvan and J.X. Rampon,
    Discrete Applied Mathematics 51 (1994), 85-93. [pdf]

  7. The Complexity of Partial Order Properties
    with D. Wagner, Proc. of WG'92
    Lecture Notes in Computer Science 657 (1993), 225-235. [pdf]

  8. Colorings of Diagrams of Interval Orders and alpha-Sequences of Sets
    with W.T. Trotter
    Discrete Mathematics 144 (1995), 23-32. [pdf]

  9. Tolerance Graphs and Orders
    Journal of Graph Theory 28 (1998), 129-140. [pdf]

  10. Interval Orders: Combinatorial Structure and Algorithms
    Dissertationsschrift, TU-Berlin 1992. [pdf]

  11. 3-Interval Irreducible Partially Ordered Sets
    Order 11 (1994), 97-125. [pdf]

  12. Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
    with L. Wernisch
    SIAM Journal of Computing 28 (1999), 192-209. [pdf]

  13. Balancing Pairs in Partially Ordered Sets
    with W.T. Trotter
    Combinatorics, Paul Erdös is eighty. Vol. 1.
    Bolyai Society Mathematical Studies     64 (1993), 145-157. [pdf]

  14. On the Fractional Dimension of Partially Ordered Sets
    with W.T. Trotter
    Discrete Mathematics 136 (1994), 101-117. [pdf]

  15. Trapezoid Graphs and Generalizations: Geometry and Algorithms
    with R. Müller and L. Wernisch.
    Discrete Applied Mathematics 74 (1997), 13-32. [pdf]

  16. Semi Order Dimension Two is a Comparability Invariant
    with R.H. Möhring.
    Order 15 (1998), 385-390. [pdf]

  17. On-Line Partitions of Orders
    Theoretical Computer Science 175 (1997), 283-292. [pdf]

  18. Balancing Pairs and the Cross Product Conjecture
    with G.R. Brightwell and W.T. Trotter
    Order 12 (1995), 321-335. [pdf]

  19. On the Number of Arrangements of Pseudolines
    Discrete & Computational Geometry 18 (1997), 257-267. [pdf]

  20. Markov Chains for Linear Extensions, the two dimensional case
    with L. Wernisch,
    Proceedings SODA 97, 239-247. [pdf]

  21. The Linear-Extension-Diameter of a Poset
    with K. Reuter.
    SIAM Journal on Discrete Mathematics 12 (1999), 360-373. [pdf]

  22. Triangles in Euclidean Arrangements
    with K. Kriegel.
    Discrete & Computational Geometry 22 (1999), 429-438. [pdf]

  23. Point-sets with few k-sets
    with H. Alt, F. Hurtado , M. Noy and E. Welzl.
    Proceedings SoCG 98, 200-205.
    Computational Geometry; Theory and Applications 16 (2000), 95-101. [pdf]

  24. Finite 3-Dimensional Partial Orders Which Are Not Sphere Orders
    with P.C. Fishburn and W.T. Trotter.
    Discrete Mathematics 201 (1999), 101-132. [pdf]

  25. Sweeps, Arrangements and Signotopes
    with H. Weil.
    Discrete Applied Mathematics 109 (2001), 67-94. [pdf]

  26. The Maximum Number of Edges in a Graph of Bounded Dimension, with Applications to Ring Theory,
    with G. Agnarsson and W.T. Trotter.
    Discrete Mathematics 201 (1999), 5-19. [pdf]

  27. Interval Reductions and Extensions of Orders: Bijections to Chains in Lattices
    with J. Gustedt and M. Morvan.
    Order 15 (1999), 221-246. [pdf]

  28. Dimension, Graph and Hypergraph Coloring
    with W.T. Trotter.
    Order 17 (2000), 167-177. [pdf]

  29. Posets and Planar Graphs
    with W.T. Trotter.
    Journal of Graph Theory 49 (2005), 262-272. [pdf]

  30. A Theorem on Higher Bruhat Orders,
    with H. Weil.
    Discrete & Computational Geometry 23 (2000), 121--127. [pdf]

  31. Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number,
    with V. Raghavan and J. Spinrad.
    Order 20 (2003), 351-364. [pdf]

  32. Zonotopes Associated with Higher Bruhat Orders,
    with G.M. Ziegler.
    Tverberg Festschrift (B. Lindström, D.G. Rogers, J. Zaks, eds.),
    Discrete Math. 241 (2001), 301--312. [pdf]

  33. Hamiltonicity and Colorings of Arrangement Graphs,
    with F. Hurtado , M. Noy and I. Streinu.
    Discrete Applied Math. 154 (2006), 2470-2483. [pdf]

  34. The Complexity of Partial Order Properties
    with R. Kant, C. Pandu Rangan and D. Wagner.
    Order 17 (2000), 179-193. [pdf]

  35. The Skeleton of a Reduced Word and a Correspondence of Edelman and Greene
    Electron. J. Comb. 8, No.1, Research paper R10 (2001), 21 p. [pdf]

  36. Convex drawings of Planar Graphs and the Order Dimension of 3-Polytopes
    Order 18 (2001), 19-37. [pdf]

  37. Storage Area Network Optimization: Project Report
    with H. Alt and L. Scharf. [pdf]

  38. Infeasibility of Systems of Halfspaces
    with N. Morawe.
    Discrete and Computational Geometry. The Goodman-Pollack Festschrift.
    (B.Aronov, S.Basu, J.Pach, M.Sharir eds.) Algorithms and Combinatorics Vol. 25, 405-424,
    Springer Verlag 2003. [pdf]

  39. Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
    with G. Liotta and S. Wismath
    Journal of Graph Alg. and Appl. 7 (2003), 363-398. [pdf]

  40. Geodesic Embeddings and Planar Graphs [pdf]
    Order 20 (2003), 135-150.

  41. Lattice Structures from Planar Graphs
    Electron. J. Comb. 11, No.1, Research paper R15 (2004), 24 p. [pdf]

  42. Convex Drawings of 3-Connected Plane Graphs [pdf]
    with N. Bonichon and M. Mosbah
    Algorithmica 47 (2007), 399-420.

  43. Grid Orientations, (d,d+2)-Polytopes and Arrangements of Pseudolines [pdf]
    with B. Gärtner and F. Tschirschnitz
    Discrete & Computational Geometry 34 (2005), 411--437.

  44. Empty Rectangles and Graph Dimension [pdf]
    arXiv: math.CO/0601767
    additional note.

  45. Orthogonal Surfaces and Their CP-Orders [pdf]
    with Sarah Kappes
    Order 25 (2008), 19-47.

  46. Schnyder Woods and Orthogonal Surfaces [pdf]
    with Florian Zickfeld
    Discrete & Computational Geometry 40 (2008), 103--126.

  47. Parameters of Bar k-Visibility Graphs [pdf]
    with Mareike Massow
    Journal of Graph Alg. and Appl. 12 (2008) 5-27.

  48. Chordal Graphs as Intersection Graphs of Pseudosegments [pdf]
    with Cornelia Dangelmayr
    Proceedings of GD'06. LNCS 4372, 208-219.

  49. On the Number of Planar Orientations with Prescribed Degrees [pdf]
    with Florian Zickfeld
    Electron. J. Comb.. 15, No.1, Research paper R77 (2008), 41 p.

  50. Binary Labelings for Plane Quadrangulations and their Relatives [pdf]
    with Sarah Kappes, Clemens Huemer and David Orden
    Discr. Math. and Theor. Comp. Sci. (DMTCS) 12:3 (2010), 115-138.

  51. On the Order Dimension of Outerplanar Maps [pdf]
    with Johan Nilsson
    Order 28 (2011), 415-435.

  52. Bijections for Baxter Families and Related Objects [pdf]
    with Éric Fusy, Marc Noy and David Orden
    Journal of Combinatorial Theory (A) 118 (2011), 993-1020.

  53. The Complexity of Sorting with Networks of Stacks and Queues [pdf]
    with Martin Pergel
    Proceedings of ESA'08, LNCS 5193, 417-429.

  54. ULD-Lattices and Δ-Bonds [pdf]
    with Kolja Knauer
    W.T. Trotter Festschrift. Comb. Prob. and Comp. 18 (2009), 707-724.

  55. Intersection Graphs of Pseudosegments: Chordal Graphs [pdf]
    with Cornelia Dangelmayr and William T. Trotter
    Journal of Graph Alg. and Appl. 14 (2010), 199-220.

  56. Distributive Lattices, Polyhedra, and Generalized Flow [pdf]
    with Kolja Knauer
    Europ. J. Comb. 32 (2011), 45-59.

  57. Asymptotic Enumeration of Orientations [pdf]
    with Éric Fusy and Marc Noy
    Discr. Math. and Theor. Comp. Sci. (DMTCS) 12:2 (2010), 249-262
    Special Issue for Philippe Flajolet's 60th birthday

  58. Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets [pdf]
    with Mareike Massow
    SIAM Journal of Discrete Mathematics 25 (2011), 112-129.

  59. Adjacency Posets of Planar Graphs [pdf]
    with Ching Man Li and William T. Trotter
    Discrete Mathematics 310 (2010), 1097-1104.

  60. Coding and Counting Arrangements of Pseudolines [pdf]
    with Pavel Valtr
    Discrete & Computational Geometry 46 (2011), 405-416

  61. Points with Large Quadrant-Depth [pdf]
    with Roel Apfelbaum, Itay Ben-Dan, Tillmann Milzow, Rom Pinchasi, Torsten Ueckerdt and Ran Ziv
    Journal of Computational Geometry 2 (2011), 128-143.

  62. Cubic Time Recognition of Cocircuit Graphs of Uniform Oriented Matroids [pdf]
    with Ricardo Gomez, Kolja Knauer, Juan Jose Montellano-Ballesteros and Ricardo Strausz
    Europ. J. Comb. 32 (2011), 60-66.

  63. On-line chain partitions of upgrowing semi-orders [pdf]
    with Kamil Kloch, Grzegorz Matecki and Piotr Micek
    ORDER
    DOI: 10.1007/s11083-011-9228-y

  64. On-Line Chain Partitions of Orders: A Survey [pdf]
    with Bartołomiej Bosek, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki and Piotr Micek
    ORDER 29 (2012), 49-73.

  65. On-Line Dimension for Posets Excluding Two Long Incomparable Chains [pdf]
    with Tomasz Krawczyk and William T. Trotter
    ORDER,
    DOI: 10.1007/s11083-011-9222-4

  66. Approximating hitting sets of axis-parallel rectangles with opposite corners separated by a monotone curve [pdf]
    with Victor Chepoi
    -- submitted.

  67. Contact representations of planar graphs with cubes [pdf]
    with Mathew C. Francis
    Proceedings SoCG '11, 315-320
    DOI: 10.1145/1998196.1998250200-205

  68. Rectangle and Square Representations of Planar Graphs [pdf]
    -- to appear in the book "Thirty Essays in Geometric Graph Theory" edited by J. Pach.

  69. Proportional Contact Representations of Planar Graphs [pdf]
    with Muhammad Jawaherul Alam, Therese Biedl, Michael Kaufmann and Stephen G. Kobourov
    Proc. Graph Drawing 2011

  70. Linear-Time Algorithms for Rectilinear Hole-free Proportional Contact Representations [pdf]
    with Muhammad Jawaherul Alam, Therese Biedl, Andreas Gerasch, Michael Kaufmann and Stephen G. Kobourov
    Proc. ISAAC 2011

  71. Computing Cartograms with Optimal Complexity [pdf]
    with Muhammad Jawaherul Alam, Therese Biedl, Michael Kaufmann, Stephen G. Kobourov and Torsten Ueckerdt
    arXiv: 1201.0066
    Proc. SoCG 2012

  72. The Dimension of Posets with Planar Comparability or Cover Graphs [pdf]
    with William T. Trotter and Veit Wiechert
    -- submitted

  73. News about Semiantichains and Unichain Coverings [pdf]
    with Bartłomiej Bosek, Kolja Knauer, and Grzegorz Matecki
    Proc. 7th Int. CS Symp. in Russia 2012

  74. The graphs that can be drawn with one bend per edge [pdf]
    with Michael Kaufmann and Pavel Valtr

end of list
Stefan Felsner

[back to top]
update: January 2012