GraDR Individual Project 2 - Germany

This a part of the Collaborative Research Project GraDR. It consists of four participating sites: Julius-Maximilians-Universität in Würzburg, Technische Universitüt in Berlin, Technische Universität in Dortmund and Eberhard Karls Universität Tübingen. The leader of this individual project is Stefan Felsner.

The team consists of the following people:

• Leader: Michael Kaufmann
• Senior Researchers: Stephen G. Kobourov (august 2011 - august 2012)
• Post-docs: Michael A. Bekos (since april 2012), Tamara Mchedlidze (march 2011 - september 2011)
• Students: Till Bruckdorfer, Andreas Gerasch, Markus Geyer, Robert Krug, Vincenzo Roselli (september 2012 - december 2012)

The team is responsible for WP12 Hypergraphs with applications in bioinformatics and participates in WP02, WP03, WP04, WP05, WP06, WP07 and WP10.

A plane bus graph is a crossing free embedded bipartite graph in which vertices of one partition will be represented as horizontal or vertical segments. These segments are associated with buses, while this drawing style (bus realization) resembles VLSI design. We have shown together with Stefan Felsner (TU Berlin) that planar bus graphs can be tested in polynomial time, whether they admit a crossing free bus realization.

• Till Bruckdorfer, Stefan Felsner, Michael Kaufmann: On the Characterization of Plane Bus Graphs. CIAC 2013: 73-84.
• Till Bruckdorfer, Stefan Felsner, Michael Kaufmann: Planar Bus Graphs, submitted 2014.

We have written three papers about a new layout for graphs called partial edge drawing.

• Till Bruckdorfer, Michael Kaufmann: Mad at Edge Crossings? Break the Edges! FUN 2012: 40-50.
• Till Bruckdorfer, Sabine Cornelsen, Carsten Gutwenger, Michael Kaufmann, Fabrizio Montecchiani, Martin Nöllenburg, Alexander Wolff: Progress on Partial Edge Drawings. Graph Drawing 2012: 67-78. Full version: http://arxiv.org/abs/1209.0830.
• Till Bruckdorfer, Michael Kaufmann, Fabrizio Montecchiani: 1-Bend Orthogonal Partial Edge Drawing. J. Graph Algorithms Appl. 18(1), pages 111-131 (2014).

Further topics:

• Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, Antonios Symvonis: Many-to-One Boundary Labeling with Backbones. Graph Drawing 2013: 244-255.
• Daniel Stöckel, Oliver Müller, Tim Kehl, Andreas Gerasch, Christina Backes, Alexander Rurainski, Andreas Keller, Michael Kaufmann, Hans-Peter Lenhof: NetworkTrail - a web service for identifying and visualizing deregulated subnetworks. Bioinformatics 29(13): 1702-1703 (2013).
• Niklas Heinsohn, Andreas Gerasch, Michael Kaufmann: Boundary Labeling Methods for Dynamic Focus Regions. PacificVis 2014: 243-247.
• Andreas Gerasch, Michael Kaufmann, Oliver Kohlbacher: Rebuilding KEGG Maps: Algorithms and Benefits. PacificVis 2014: 97-104.

• Patrizio Angelini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Anna Lubiw: RAC and LAC drawings of planar graphs in subquadratic area, In 14th Spanish Meeting on Computational Geometry (EGC '11), Centre de Recerca Matematica, volume 8 of Documents, pages 125-128, 2011.
• Aparna Das, Emden R. Gansner, Michael Kaufmann, Stephen Kobourov, Joachim Spoerhase, Alexander Wolff: Approximating Minimum Manhattan Networks in Higher Dimensions. ESA 2011: 49-60.
• Stephen Kobourov, Alexander Wolff, Frank van Ham: Putting Data on the Map (Dagstuhl Seminar 12261), Dagstuhl Reports 2(6), pages 51-76, 2012.
• Aparna Das, Krzysztof Fleszar, Stephen G. Kobourov, Joachim Spoerhase, Sankar Veeramoni, Alexander Wolff: Polylogarithmic Approximation for Generalized Minimum Manhattan Networks, Arxiv report, 2012, http://arxiv.org/abs/1203.6481.
• Patrizio Angelini, Giuseppe Di Battista, Walter Didimo, Fabrizio Frati, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Anna Lubiw: Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area. EGC 2011: 200-209.
• Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Yoshio Okamoto, Andreas Spillner: Vertex angle and crossing angle resolution of leveled tree drawings. Inf. Process. Lett. 112(16): 630-635 (2012).
• Evmorfia N. Argyriou, Michael A. Bekos, Michael Kaufmann, Antonios Symvonis: Geometric RAC Simultaneous Drawings of Graphs. COCOON 2012: 287-298.
• Michael A. Bekos, Michael Kaufmann, Robert Krug, Stefan Näher, Vincenzo Roselli: Slanted Orthogonal Drawings. Graph Drawing 2013: 424-435.
• Michael A. Bekos, Michael Kaufmann, Stephen G. Kobourov, Antonios Symvonis: Smooth Orthogonal Layouts. J. Graph Algorithms Appl. 17(5): 575-595 (2013).
• Md. Jawaherul Alam, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Stephen G. Kobourov, Alexander Wolff: Smooth Orthogonal Drawings of Planar Graphs. LATIN 2014: 144-155.
• Michael A. Bekos, Michael Kaufmann, Robert Krug: Sloggy drawings of graphs. IISA 2014: 82-87.
• Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Robert Krug: Planar Octilinear Drawings with One Bend Per Edge. Graph Drawing 2014: 331-342.
• Michael A. Bekos, Sabine Cornelsen, Luca Grilli, Seok-Hee Hong, Michael Kaufmann: On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs. Graph Drawing 2014: 198-209.

• Patrizio Angelini, Markus Geyer, Michael Kaufmann, Daniel Neuwirth: On a Tree and a Path with no Geometric Simultaneous Embedding. J. Graph Algorithms Appl. 16(1): 37-83 (2012).
• Markus Geyer, Michael Hoffmann, Michael Kaufmann, Vincent Kusters, Csaba D. Tóth: Planar Packing of Binary Trees, WADS 2013: 353-364.
• Evmorfia N. Argyriou, Michael A. Bekos, Michael Kaufmann, Antonios Symvonis: Geometric RAC Simultaneous Drawings of Graphs. J. Graph Algorithms Appl. 17(1): 11-34 (2013).
   

• Stefan Felsner, Michael Kaufmann, Pavel Valtr: The graphs that can be drawn with one bend per edge, Full version submitted to special DAM issue for EuroCG.
• Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, Claudio Squarcella: On the Area Requirements of Euclidean Minimum Spanning Trees, WADS 2011: 25-36.
• Fabrizio Frati, Michael Kaufmann, János Pach, Csaba D. Tóth, David R. Wood: On the Upward Planarity of Mixed Plane Graphs. Graph Drawing 2013: 1-12.
• Patrizio Angelini, David Eppstein, Fabrizio Frati, Michael Kaufmann, Sylvain Lazard, Tamara Mchedlidze, Monique Teillaud, Alexander Wolff: Universal Point Sets for Planar Graph Drawings with Circular Arcs. CCCG 2013.
• Michael Kaufmann, Tamara Mchedlidze, Antonios Symvonis: On upward point set embeddability. Comput. Geom. 46(6): 774-804 (2013).
• William S. Evans, Emden R. Gansner, Michael Kaufmann, Giuseppe Liotta, Henk Meijer, Andreas Spillner: Approximate proximity drawings. Comput. Geom. 46(6): 604-614 (2013).
• Emilio Di Giacomo, Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Fabrizio Montecchiani: Upward-rightward planar drawings. IISA 2014: 145-150.
• Patrizio Angelini, David Eppstein, Fabrizio Frati, Michael Kaufmann, Sylvain Lazard, Tamara Mchedlidze, Monique Teillaud, Alexander Wolff: Universal Point Sets for Drawing Planar Graphs with Circular Arcs. J. Graph Algorithms Appl. 18(3): 313-324 (2014).
• Fabrizio Frati, Michael Kaufmann, János Pach, Csaba D. Tóth, David R. Wood: On the Upward Planarity of Mixed Plane Graphs. J. Graph Algorithms Appl. 18(2): 253-279 (2014).
• Stefan Felsner, Michael Kaufmann, Pavel Valtr: Bend-optimal orthogonal graph drawing in the general position model. Comput. Geom. 47(3): 460-468 (2014).
• Patrizio Angelini, Till Bruckdorfer, Marco Chiesa, Fabrizio Frati, Michael Kaufmann, Claudio Squarcella: On the area requirements of Euclidean minimum spanning trees. Comput. Geom. 47(2): 200-213 (2014).

• Patrizio Angelini, Giuseppe Di Battista, Michael Kaufmann, Tamara Mchedlidze, Vincenzo Roselli, Claudio Squarcella: Small Point Sets for Simply-Nested Planar Graphs, Graph Drawing 2011: 75-85.
• Patrizio Angelini, Fabrizio Frati, Michael Kaufmann: Straight-Line Rectangular Drawings of Clustered Graphs. Discrete & Computational Geometry 45(1): 88-140 (2011).
• Md. Jawaherul Alam, Michael Kaufmann, Stephen Kobourov, Tamara Mchedlidze: Fitting Planar Graphs on Planar Maps. SOFSEM 2014: 52-64.

• Michael A. Bekos, Sabine Cornelsen, Luca Grilli, Seok-Hee Hong, Michael Kaufmann: On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs. Graph Drawing 2014: 198-209.

• Md. Jawaherul Alam, Michael Kaufmann, Stephen G. Kobourov, Tamara Mchedlidze: Fitting Planar Graphs on Planar Maps. SOFSEM 2014: 52-64.
• William S. Evans, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Debajyoti Mondal, Rahnuma Islam Nishat, Kevin Verbeek: Table Cartograms. ESA 2013: 421-432.

• Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov: Proportional Contact Representations of Planar Graphs. Graph Drawing 2011: 26-38.
• Md. Jawaherul Alam, Therese C. Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, Stephen G. Kobourov: Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations. ISAAC 2011: 281-291.
• Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Torsten Ueckerdt: Computing Cartograms with Optimal Complexity. Symposium on Computational Geometry 2012: 21-30.
• Md. Jawaherul Alam, Steven Chaplick, Gasper Fijavz, Michael Kaufmann, Stephen G. Kobourov, Sergey Pupyrev: Threshold-Coloring and Unit-Cube Contact Representation of Graphs. WG 2013: 26-37.
• Md. Jawaherul Alam, Therese C. Biedl, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Torsten Ueckerdt: Computing Cartograms with Optimal Complexity. Discrete & Computational Geometry 50(3): 784-810 (2013).
• Md. Jawaherul Alam, Therese C. Biedl, Stefan Felsner, Andreas Gerasch, Michael Kaufmann, Stephen G. Kobourov: Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations. Algorithmica 67(1): 3-22 (2013).