Stefan Felsner's Publications

Link to [end of list]

  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, Proceedings WG 92 LNCS 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
    Proceedings WG 92 LNCS 657 (1993), 17-26.
    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.
    Proceedings SWAT 94 LNCS 824 (1994), 143-154.
    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
    Proceedings SoCG 96, 30-37.
    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.
    Proceedings WG 98 LNCS 1517, 137-148.
    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), 273-284. [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.
    Proceedings SODA 2000, 155-164.
    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
    Proceedings GD 01 LNCS 2265, 328-342.
    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
    Proceedings GD 04 LNCS 3383, 60-70.
    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
    Proceedings GD 06 LNCS 4372, 417-429.
    Discrete & Computational Geometry 40 (2008), 103--126.

  47. Parameters of Bar k-Visibility Graphs [pdf]
    with Mareike Massow
    Proceedings GD 06 LNCS 4372, 330-342.
    Journal of Graph Alg. and Appl. 12 (2008) 5-27.

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

  49. On the Number of Planar Orientations with Prescribed Degrees [pdf]
    with Florian Zickfeld
    Proceedings WG 07 LNCS 4769, 190-201.
    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 30 (2013), 85-101.

  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 30 (2012), 1-12.

  66. Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve [pdf]
    with Victor Chepoi
    CGTA 46 (2013),1036-1041.

  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]
    in "Thirty Essays in Geometric Graph Theory" edited by J. Pach, 213-248
    Springer New York, 2012

  69. Proportional Contact Representations of Planar Graphs [pdf]
    with Muhammad Jawaherul Alam, Therese Biedl, Michael Kaufmann and Stephen G. Kobourov
    Proceedings GD 11, LNCS 7034, 26-38.
    Journal of Graph Alg. and Appl. 16 (2012), 701-728.

  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
    Proceedings ISAAC 11, LNCS 7074, 281-291.
    Algorithmica 67 (2013) 3,-22.

  71. Computing Cartograms with Optimal Complexity [pdf]
    with Muhammad Jawaherul Alam, Therese Biedl, Michael Kaufmann, Stephen G. Kobourov and Torsten Ueckerdt
    Proceedings SoCG 2012, 21-30.
    Discrete & Computational Geometry 50 (2013) 784-810.

  72. The Dimension of Posets with Planar Cover Graphs [pdf]
    with William T. Trotter and Veit Wiechert
    Graphs and Combinatorics 31 (2015) 927-939.

  73. News about Semiantichains and Unichain Coverings [pdf]
    with Bartłomiej Bosek, Kolja Knauer, and Grzegorz Matecki
    Proceedings CSR 12, LNCS 7353, 43-51.
    ORDER 33 (2016) 29-38.

  74. Bend-optimal orthogonal graph drawing in the general position model [pdf]
    with Michael Kaufmann and Pavel Valtr
    CGTA 47 (2014) 460-468.

  75. On the Characterization of Plane Bus Graphs [pdf]
    with Till Bruckdorfer and Michael Kaufmann
    Proceedings CIAC 13, LNCS 7878, 73-84.
    Full version Planar Bus Graphs, to appear in Algorithmica. DOI: 10.1007/s00453-017-0321-5

  76. Exploiting Air-Pressure to Map Floorplans on Point Sets [pdf]
    Proceedings GD 13, LNCS 8242, 196-207.
    JGAA 18 (2014) 233-252

  77. Straight Line Triangle Representations [pdf]
    with Nieke Aerts
    Proceedings GD 13, LNCS 8242, 120-131.
    Discrete & Computational Geometry 57 (2017) 257-280.

  78. Table Cartograms [pdf]
    with William Evans, Michael Kaufmann, Stephen G. Kobourov, Debajyoti Mondal, Rahnuma Islam Nishat, and Kevin Verbeek
    Proceedings ESA 13, LNCS 8125, 421-432.
    full version to appear in Special Issue of CGTA in memoriam: Ferran Hurtado/BR DOI: 10.1016/j.comgeo.2017.06.010

  79. On the Recognition of Four-Directional Orthogonal Ray Graphs
    with George B. Mertzios and Irina Mustata
    Proceedings MFCS 13, LNCS 8087, 373-384.

  80. The Order Dimension of Planar Maps Revisited [pdf]
    SIDMA 28 (2014) 1093-1101.

  81. Linear Extensions of N-free Orders [pdf]
    with Thibault Manneville
    Order, 32 (2015) 147-155.

  82. Covering Partial Cubes with Zones [pdf]
    with Jean Cardinal
    Postproceedings JCDCG2 2013, LNCS 8845 (2014) 1-13.
    Electron. J. Comb. 22, No.3, Research paper #P3.31 (2015), 18p.

  83. Drawing HV-Restricted Planar Graphs [pdf]
    with Stephane Durocher, Saeed Mehrabi, and Debajyoti Mondal
    Proceedings LATIN 2014, LNCS 8392 (2014) 156-167

  84. Max Point-Tolerance Graphs [pdf]
    with Daniele Catanzaro, Steven Chaplick, Bjarni V. Halldorsson, Magnus M. Halldorsson, Thomas Hixon, and Juraj Stacho
    Special Volume in honor of Andreas Brandstädt
    Discrete Applied Math. 216 (2017) 84-97.

  85. Intersection Graphs of L-Shapes and Segments in the Plane [pdf]
    with Kolja Knauer, George B. Mertzios, and Torsten Ueckerdt
    Proceedings MFCS 14, LNCS 8635 (2014) 299-310.
    Discrete Applied Math. 206 (2016), 48-55.

  86. Graphs admitting d-realizers: spanning-tree-decompositions and box-representations [pdf]
    with William Evans, Stephen G. Kobourov, and Torsten Ueckerdt
    Proceedings EuroCG 14.

  87. Vertex Contact Graphs of Paths on a Grid [pdf]
    with Nieke Aerts
    Proceedings WG 14, LNCS 8747 (2014) 56-68.
    JGAA 19 (2015) 817-849.

  88. Straight-Line Triangle Representations via Schnyder Labelings [pdf]
    with Nieke Aerts
    Proceedings GD 13 LNCS 8242, 119-130.
    JGAA 19 (2015) 467-505.

  89. Henneberg steps for triangle representations [pdf]
    with Nieke Aerts
    Proceedings EuroComb 2013 CRM-Series, Vol 16, 503-509
    DOI: 10.1007/978-88-7642-475-5_80
    Full version

  90. Grid Intersection Graphs and Order Dimension [pdf]
    with Steve Chaplick, Udo Hoffmann, and Veit Wiechert
    arXiv: 1512.02482
    ORDER accepted

  91. Ham-Sandwich Cuts for Abstract Order Types [pdf]
    with Alexander Pilz,
    Proceedings ISAAC 14, LNCS 8889 (2014) 726-737.
    ALGO accepted
    DOI: 10.1007/s00453-016-0246-4

  92. The Complexity of the Partial Order Dimension Problem - Closing the Gap [pdf]
    with Irina Mustaţă and Martin Pergel
    SIAM J. Discr. Math. 31 (2017), 172-189.

  93. Lattice path enumeration and Toeplitz matrices [pdf]
    with Daniel Heldt
    Journal of Integer Sequences (JIS) Vol. 18, Article 15.1.3 (2015) 15 pages.

  94. On-line coloring between two lines [pdf]
    with Piotr Micek and Torsten Ueckerdt
    Proceedings SoCG 15, LIPIcs 34 (2015) 630-641.

  95. Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs [pdf]
    with Daniel Heldt
    Proceedings WALCOM 16, LNCS 9627 (2016) 114-127.
    Discr. Math. and Theor. Comp. Sci. (DMTCS) 18:3 (2016), #20.

  96. Pseudoline Arrangements [pdf]
    with Jacob E. Goodman
    Chapter 5 in Handbook of Discrete and Computational Geometry 3rd edition, CRC Press 2016.

  97. Strongly Monotone Drawings of Planar Graphs [pdf]
    with Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze and Manfred Scheucher
    Proceedings SoCG 16 LIPIcs 51 (2016) 37:1--37:15.

  98. Shifting Segments to Optimality [pdf]
    in "Gems of Combinatorial Optimization and Graph Algorithms (a homage to R.H. Möhring)"
    edited by A.S. Schulz et al., 1-12, Springer 2015

  99. Topological Drawings of Complete Bipartite Graphs [pdf]
    with Jean Cardinal
    Proceedings GD'16, LNCS 9801 (2016) 441-453.

  100. Intersection Graphs of Rays and Grounded Segments [pdf]
    with Jean Cardinal, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber
    Proceedings WG'17, LNCS 10520 (2017)

  101. Ramsey Theory for Binary Trees and the Separation of Tree-chromatic Number from Path-chromatic Number [pdf]
    with Fidel Barrera-Cruz, Tamás Mészáros, Piotr Micek, Heather Smith, Libby Taylor, William T. Trotter

  102. Arrangements of Approaching Pseudo-Lines [pdf]
    with Alexander Pilz,
    Proceedings EuroCG 17.

  103. Triangles in Arrangements of Pseudocircles [pdf]
    with Manfred Scheucher,
    Proceedings EuroCG 17.
    Arrangements of Pseudocircles: Triangles and Drawings [pdf]
    Proceedings GD 17.
    Supplementary material at the "Pseudopage of circles"

  104. Pentagon contact representations [pdf]
    with Hendrik Schrezenmaier and Raphael Steiner
    Extended Abstract in ENDM issue Eurocomb 2017 [endm] [pdf]

  105. Burling graphs, chromatic number, and orthogonal tree-decompositions [pdf]
    with Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert
    Extended Abstract in ENDM issue Eurocomb 2017 [endm]

  106. On the Maximum Crossing Number [pdf]
    with Markus Chimani, Stephen Kobourov, Torsten Ueckerdt, Pavel Valtr, and Alexander Wolff
    Extended Abstract at IWOCA

  107. Boolean dimension and tree-width [pdf]
    with Tamás Mészáros and Piotr Micek

  108. Equiangular polygon contact representations [pdf]
    with Hendrik Schrezenmaier and Raphael Steiner

end of list
Stefan Felsner

[back to top]
update: July 2017