Graph Drawing and Network Visualization: 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers

Description

This book constitutes revised selected papers from the 25th International Symposium on Graph Drawing and Network Visualization, GD 2017, held in Boston, MA, USA, in September 2017.The 34 full and 9 short papers presented in this volume were carefully reviewed and selected from 87 submissions. Also included in this book are 2 abstracts of keynote presentations, 16 poster abstracts, and 1 contest report. The papers are organized in topical sections named: straight-line representations; obstacles and visibility; topological graph theory; orthogonal representations and book embeddings; evaluations; tree drawings; graph layout designs; point-set embeddings; special representations; and beyond planarity. Front Matter ....Pages I-XX Front Matter ....Pages 1-1 Aligned Drawings of Planar Graphs (Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter)....Pages 3-16 On the Edge-Length Ratio of Outerplanar Graphs (Sylvain Lazard, William Lenhart, Giuseppe Liotta)....Pages 17-23 On Vertex- and Empty-Ply Proximity Drawings (Patrizio Angelini, Steven Chaplick, Felice De Luca, Jiří Fiala, Jaroslav Hančl Jr., Niklas Heinsohn et al.)....Pages 24-37 An Interactive Tool to Explore and Improve the Ply Number of Drawings (Niklas Heinsohn, Michael Kaufmann)....Pages 38-51 Experimental Analysis of the Accessibility of Drawings with Few Segments (Philipp Kindermann, Wouter Meulemans, André Schulz)....Pages 52-64 Front Matter ....Pages 65-65 Obstacle Numbers of Planar Graphs (John Gimbel, Patrice Ossona de Mendez, Pavel Valtr)....Pages 67-80 Grid-Obstacle Representations with Connections to Staircase Guarding (Therese Biedl, Saeed Mehrabi)....Pages 81-87 Reconstructing Generalized Staircase Polygons with Uniform Step Length (Nodari Sitchinava, Darren Strash)....Pages 88-101 3D Visibility Representations of 1-planar Graphs (Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Fabrizio Montecchiani)....Pages 102-109 Front Matter ....Pages 111-111 Lombardi Drawings of Knots and Links (Philipp Kindermann, Stephen Kobourov, Maarten Löffler, Martin Nöllenburg, André Schulz, Birgit Vogtenhuber)....Pages 113-126 Arrangements of Pseudocircles: Triangles and Drawings (Stefan Felsner, Manfred Scheucher)....Pages 127-139 Drawing Bobbin Lace Graphs, or, Fundamental Cycles for a Subclass of Periodic Graphs (Therese Biedl, Veronika Irvine)....Pages 140-152 Many Touchings Force Many Crossings (János Pach, Géza Tóth)....Pages 153-159 Thrackles: An Improved Upper Bound (Radoslav Fulek, János Pach)....Pages 160-166 Front Matter ....Pages 167-167 On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings (Michael A. Bekos, Henry Förster, Michael Kaufmann)....Pages 169-183 EPG-representations with Small Grid-Size (Therese Biedl, Martin Derka, Vida Dujmović, Pat Morin)....Pages 184-196 Mixed Linear Layouts of Planar Graphs (Sergey Pupyrev)....Pages 197-209 Upward Partitioned Book Embeddings (Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Quanquan C. Liu)....Pages 210-223 Experimental Evaluation of Book Drawing Algorithms (Jonathan Klawitter, Tamara Mchedlidze, Martin Nöllenburg)....Pages 224-238 Front Matter ....Pages 239-239 Visual Similarity Perception of Directed Acyclic Graphs: A Study on Influencing Factors (K. Ballweg, M. Pohl, G. Wallner, T. von Landesberger)....Pages 241-255 GiViP: A Visual Profiler for Distributed Graph Processing Systems (Alessio Arleo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani)....Pages 256-271 Drawing Big Graphs Using Spectral Sparsification (Peter Eades, Quan Nguyen, Seok-Hee Hong)....Pages 272-286 Revisited Experimental Comparison of Node-Link and Matrix Representations (Mershack Okoe, Radu Jianu, Stephen Kobourov)....Pages 287-302 Front Matter ....Pages 303-303 Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges (Therese Biedl, Timothy M. Chan, Martin Derka, Kshitij Jain, Anna Lubiw)....Pages 305-317 On Upward Drawings of Trees on a Given Grid (Therese Biedl, Debajyoti Mondal)....Pages 318-325 Simple Compact Monotone Tree Drawings (Anargyros Oikonomou, Antonios Symvonis)....Pages 326-333 Visualizing Co-phylogenetic Reconciliations (Tiziana Calamoneri, Valentino Di Donato, Diego Mariottini, Maurizio Patrignani)....Pages 334-347 Front Matter ....Pages 349-349 Anisotropic Radial Layout for Visualizing Centrality and Structure in Graphs (Mukund Raj, Ross T. Whitaker)....Pages 351-364 Computing Storyline Visualizations with Few Block Crossings (Thomas C. van Dijk, Fabian Lipp, Peter Markfelder, Alexander Wolff)....Pages 365-378 MLSEB: Edge Bundling Using Moving Least Squares Approximation (Jieting Wu, Jianping Zeng, Feiyu Zhu, Hongfeng Yu)....Pages 379-393 Drawing Dynamic Graphs Without Timeslices (Paolo Simonetto, Daniel Archambault, Stephen Kobourov)....Pages 394-409 Front Matter ....Pages 411-411 Colored Point-Set Embeddings of Acyclic Graphs (Emilio Di Giacomo, Leszek Gasieniec, Giuseppe Liotta, Alfredo Navarra)....Pages 413-425 Planar Drawings of Fixed-Mobile Bigraphs (Michael A. Bekos, Felice De Luca, Walter Didimo, Tamara Mchedlidze, Martin Nöllenburg, Antonios Symvonis et al.)....Pages 426-439 Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity (Boris Klemz, Günter Rote)....Pages 440-453 Non-crossing Paths with Geographic Constraints (Rodrigo I. Silveira, Bettina Speckmann, Kevin Verbeek)....Pages 454-461 Front Matter ....Pages 463-463 Planar L-Drawings of Directed Graphs (Steven Chaplick, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Martin Nöllenburg, Maurizio Patrignani et al.)....Pages 465-478 NodeTrix Planarity Testing with Small Clusters (Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, Alessandra Tappini)....Pages 479-491 The Painter’s Problem: Covering a Grid with Colored Connected Polygons (Arthur van Goethem, Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Max Sondag, Jules Wulms)....Pages 492-505 Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count (David Eppstein)....Pages 506-513 Front Matter ....Pages 515-515 1-Fan-Bundle-Planar Drawings of Graphs (Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Philipp Kindermann, Thomas Schneck)....Pages 517-530 Gap-Planar Graphs (Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli et al.)....Pages 531-545 Beyond Outerplanarity (Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, Alexander Wolff)....Pages 546-559 The Effect of Planarization on Width (David Eppstein)....Pages 560-572 Front Matter ....Pages 573-573 Graph Drawing Contest Report (William Devanny, Philipp Kindermann, Maarten Löffler, Ignaz Rutter)....Pages 575-582 Back Matter ....Pages 583-634