Graph Drawings and Representations
Final Report Abstract
This project was part of the EuroGIGA collaborative research project GraDR - Graph Drawings and Representations archives.esf.org/coordinating-research/eurocores/programmes/eurogiga/collaborative-research-projects.html#c83561. The main goal of the project was to foster collaborative research in the areas of graph drawing and geometric representations of graphs. This has certainly been achieved. More than 100 publications stemming from the project speak for itself. At the 23rd International Symposium Graph Drawing 2015 (held in Los Angeles), 23 (that is more than 50%) are co-authored by researchers that have been members of GraDR CRP at least for some time of the life of the project. Many of them are former PhD students or postdocs in the project, and this shows that the second main goal of the project (transfer of our knowhow to the next generation) has been successfully fulfilled as well. Another outstanding appreciation of the quality of the team was an invitation to deliver an invited lecture at the ICM 2014. János Pach, acknowledged the support from GraDR in his paper János Pach: Geometric intersection patterns and the theory of geometric graphs, presented at the International Congress of Mathematicians 2014 in Seoul, Korea. The Berlin branch of the project was lead by Stefan Felsner. The special focus of this group was on the work packages “constrained embeddings”, “quasi- and near-planar graphs”, and “contact and intersection representations”.
Publications
- Algorithms for Labeling Focus Regions, IEEE Trans. Vis. Comput. Graphics 18(12) (2012), 2583–2592
Martin Fink, Jan-Henrik Haunert, André Schulz, Joachim Spoerhase, Alexander Wolff
(See online at https://doi.org/10.1109/TVCG.2012.193) - Vertex Insertion approximates the Crossing Number for Apex Graphs, European J. Combinatorics 33 (2012), 326–335
Markus Chimani, Petr Hliněný, Petra Mutzel
(See online at https://doi.org/10.1016/j.ejc.2011.09.009) - Computing Cartograms with Optimal Complexity. Discrete & Computational Geometry, Vol. 50. 2013, pp. 784–810.
Md. Jawaherul Alam, Therese Biedl, Stefan Felsner, Michael Kaufmann, Stephen G. Kobourov, Torsten Ueckerdt
(See online at https://doi.org/10.1007/s00454-013-9521-1) - On the Queue Number of Planar Graphs, SIAM Journal on Computing 42(6):2243–2285, 2013
Giuseppe Di Battista, Fabrizio Frati, János Pach
(See online at https://doi.org/10.1137/130908051) - Planar Graphs as VPG-Graphs. Special Issue on Selected Papers from the Twentieth International Symposium on Graph Drawing, GD 2012. Journal of Graph Algorithms and Applications, Vol. 17. 2013, no. 4, pp. 475-494.
Steven Chaplick, Torsten Ueckerdt
(See online at https://dx.doi.org/10.7155/jgaa.00300) - Bend-optimal orthogonal graph drawing in the general position model,
Computational Geometry, Vol. 47. 2014, Issue 3, Part B, pp. 460-468.
Stefan Felsner, Michael Kaufmann, Pavel Valtr
(See online at https://doi.org/10.1016/j.comgeo.2013.03.002) - Exploiting Air-Pressure to Map Floorplans on Point Sets. Special Issue on Selected Papers from the Twenty-first International Symposium on Graph Drawing, GD 2013. Journal of Graph Algorithms and Applications, Vol. 18. 2014, no. 2, pp. 233-252.
Stefan Felsner
(See online at https://dx.doi.org/10.7155/jgaa.00320) - The Order Dimension of Planar Maps Revisited. SIAM Journal on Discrete Mathematics, Vol. 28.2014, Issue 3, pp. 1093–1101.
Stefan Felsner
(See online at https://doi.org/10.1137/130945284) - Testing Planarity of Partially Embedded Graphs, ACM Transactions on Algorithms, 11(4): Article No. 32 (2015)
Patrizio Angelini, Giuseppe Di Battista, Fabrizio Frati, Vít Jelínek, Jan Kratochvíl, Maurizio Patrignani, Ignaz Rutter
(See online at https://doi.org/10.1145/2629341)
