
Martin Fink
Postdoctoral Fellow
Department of Computer Science
Harold Frank Hall
University of California, Santa Barbara, 93106
email: fink at cs.ucsb.edu

Research Interests
 Graph Drawing
 Computational Geometry
 Graph Algorithms
Publications
Improved Approximation Algorithms for Box Contact Representations.
Algorithmica:119, 2016.
Michael A. Bekos, Thomas C. Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff.
[doi]
[abstract]
[BibTeX]
We study the following geometric representation problem: Given a graph whose vertices correspond to axisaligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NPhard, and there are approximation algorithms for certain graph classes for the optimization version, MaxCrown, in which realizing each desired adjacency yields a certain profit. We present the first O(1)approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APXcomplete on bipartite graphs of bounded maximum degree.
Bundled Crossings in Embedded Graphs.
In: E. Kranakis, G. Navarro and E. Chávez, editors,
LATIN 2016: Theoretical Informatics  12th Latin American Symposium, Ensenada, Mexico, April 1115, 2016, Proceedings, volume 9644, series Lecture Notes in Computer Science, pages 454468.
Springer, 2016.
Martin Fink, John Hershberger, Subhash Suri and Kevin Verbeek.
[doi]
[BibTeX]
ManytoOne Boundary Labeling with Backbones.
Journal of Graph Algorithms and Applications, 19(3):779816, 2015.
Michael A. Bekos, Sabine Cornelsen, Martin Fink, SeokHee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter and Antonios Symvonis.
[doi]
[BibTeX]
Ordering Metro Lines by Block Crossings.
Journal of Graph Algorithms and Applications, 19(1):111153, 2015.
Martin Fink, Sergey Pupyrev and Alexander Wolff.
[doi]
[abstract]
[BibTeX]
A problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging single crossings into <em>block crossings</em>, that is, crossings of two neighboring groups of consecutive lines.
Unfortunately, minimizing the total number of block crossings is NPhard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worstcase optimal algorithm for block crossings on general graphs. Furthermore, we show that the problem remains NPhard on planar graphs even if both the maximum degree and the number of lines per edge are bounded by constants; on trees, this restricted version becomes tractable.
Tradeoffs between Bends and Displacement in Anchored Graph Drawing..
In:
Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 1012, 2015.
Queen's University, Ontario, Canada, 2015.
Martin Fink and Subhash Suri.
[doi]
[BibTeX]
Drawing Graphs within Restricted Area.
In: C. Duncan and A. Symvonis, editors,
Proceedings of the 22nd International Symposium on Graph Drawing (GD '14), volume 8871, series Lecture Notes in Computer Science, pages 367379.
SpringerVerlag, 2014.
Maximilian Aulbach, Martin Fink, Julian Schuhmann and Alexander Wolff.
[doi]
[abstract]
[BibTeX]
We study the problem of selecting a maximumweight subgraph of a given graph such that the subgraph can be drawn within a prescribed drawing area subject to given nonuniform vertex sizes. We develop and analyze heuristics both for the general (undirected) case and for the use case of (directed) <em>calculation graphs</em> which are used to analyze the typical mistakes that high school students make when transforming mathematical expressions in the process of calculating, for example, sums of fractions.
Improved Approximation Algorithms for Box Contact Representations.
In: A. S. Schulz and D. Wagner, editors,
Proceedings of the 22nd European Symposium on Algorithms (ESA '14), volume 8737, series Lecture Notes in Computer Science, pages 8799.
SpringerVerlag, 2014.
Michael A. Bekos, Thomas C. van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase and Alexander Wolff.
[doi]
[abstract]
[BibTeX]
We study the following geometric representation problem: Given a
graph whose vertices correspond to axisaligned rectangles with
fixed dimensions, arrange the rectangles without overlaps in the
plane such that two rectangles touch if the graph
contains an edge between them. This problem is called
Contact Representation of Word Networks (Crown) since
it formalizes the geometric problem
behind drawing word clouds in which semantically related words are
close to each other. Crown is known to be
NPhard, and there are approximation algorithms for certain graph
classes for the optimization version, MaxCrown, in which realizing
each desired adjacency yields a certain profit.
We present the first $O(1)$approximation algorithm for the general
case, when the input is a complete weighted graph, and for the
bipartite case. Since the
subgraph of realized adjacencies is necessarily planar, we also consider
several planar graph classes (namely stars, trees, outerplanar, and
planar graphs), improving upon the known results.
For some graph classes, we also describe improvements
in the unweighted case, where each adjacency yields the same
profit. Finally, we show that the problem is APXhard on
bipartite graphs of bounded maximum degree.
Concentric Metro Maps.
In: M. J. Roberts and P. Rodgers, editors,
Abstracts of the Schematic Mapping Workshop 2014.
2014.
Martin Fink, Magnus Lechner and Alexander Wolff.
[doi]
[BibTeX]
Crossings, Curves, and Constraints in Graph Drawing.
PhD thesis, Universität Würzburg, 2014.
Martin Fink.
[doi]
[BibTeX]
ManytoOne Boundary Labeling with Backbones.
In: S. Wismath and A. Wolff, editors,
Proc. 21st Int. Sympos. Graph Drawing (GD'13), volume 8242, series Lecture Notes in Computer Science, pages 244255.
SpringerVerlag, 2013.
Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seokhee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter and Antonios Symvonis.
[doi] [pdf]
[abstract]
[BibTeX]
In this paper we introduce and study manytoone boundary labeling with backbone leaders. In this new manytoone model, a horizontal backbone reaches out of each label into the featureenclosing rectangle. Feature points that need to be connected to this label are linked via vertical line segments to the backbone. We present dynamic programming algorithms for label number and total leader length minimization of crossingfree backbone labelings. When crossings are allowed, we aim to obtain solutions with the minimum number of crossings. This can be achieved efficiently in the case of fixed label order, however, in the case of flexible label order we show that minimizing the number of leader crossings is NPhard.
Drawing Metro Maps using Bézier Curves.
In: W. Didimo and M. Patrignani, editors,
Proc. 20th Int. Sympos. Graph Drawing (GD'12), volume 7704, series Lecture Notes in Computer Science, pages 463474.
SpringerVerlag, 2013.
Martin Fink, Herman Haverkort, Martin Nöllenburg, Maxwell Roberts, Julian Schuhmann and Alexander Wolff.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
The automatic layout of metro maps has been investigated quite intensely over the last few years. Previous work has focused on the octilinear drawing style where edges are drawn horizontally, vertically, or diagonally at 45°. Inspired by manually created curvy metro maps, we advocate the use of the curvilinear drawing style; we draw edges as Bézier curves. Since we forbid metro lines to bend (even in stations), the user of such a map can trace the metro lines easily. In order to create such drawings, we use the forcedirected framework. Our method is the first that directly represents and operates on edges as curves.
MetroLine Crossing Minimization: Hardness, Approximations, and Tractable Cases.
In: S. Wismath and A. Wolff, editors,
Proc. 21st Int. Sympos. Graph Drawing (GD'13), volume 8242, series Lecture Notes in Computer Science, pages 328339.
SpringerVerlag, 2013.
Martin Fink and Sergey Pupyrev.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
Crossing minimization is one of the central problems in graph drawing. Recently, there has been an increased interest in the problem of minimizing crossings between paths in drawings of graphs. This is the metroline crossing minimization problem (MLCM): Given an embedded graph and a set L of simple paths, called lines, order the lines on each edge so that the total number of crossings is minimized. So far, the complexity of MLCM has been an open problem. In contrast, the problem variant in which line ends must be placed in outermost
position on their edges (MLCMP) is known to be NPhard.
Our main results answer two open questions: (i) We show that MLCM is NPhard. (ii) We give an $O(log L)$approximation algorithm for MLCMP.
Ordering Metro Lines by Block Crossings.
In: K. Chatterjee and J. Sgall, editors,
Proc. 38th Int. Sympos. Mathematical Foundations of Computer Science (MFCS'13), volume 8087, series Lecture Notes in Computer Science, pages 397408.
SpringerVerlag, 2013.
Martin Fink and Sergey Pupyrev.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
A problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging crossings into block crossings, that is, crossings of two neighboring groups of consecutive lines. Unfortunately, minimizing the total number of block crossings is NPhard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worstcase optimal algorithm for block crossings on general graphs.
Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation.
IEEE Transactions on Visualization and Computer Graphics, 19(12):23262335, 2013.
Martin Fink, JanHenrik Haunert, Joachim Spoerhase and Alexander Wolff.
[doi] [pdf]
[abstract]
[BibTeX]
Scatter plots are diagrams that visualize twodimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the xcoordinates of the points in Q by s and the ycoordinates by 1/s yields a point set P(s) that
optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on realworld instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize.
In conclusion, minimizing the total edge length and minimizing what we call the “uncompactness” of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.
Selecting the Aspect Ratio of a Scatter Plot Based on Its Delaunay Triangulation.
In: Sá. Fekete, editor,
Proc. 29th Europ. Workshop Comput. Geom. (EuroCG'13).
Braunschweig, 2013.
Martin Fink, JanHenrik Haunert, Joachim Spoerhase and Alexander Wolff.
[pdf] [slides]
[abstract]
[BibTeX]
Scatter plots are diagrams that visualize sets of points in two dimensions. They allow users to detect correlations and clusters in the data. Whether a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot has some nice geometric property, e.g., a large minimum angle or a small total edge length. In order to find an optimum aspect ratio according to a given criterion we present an algorithm that efficiently maintains the Delaunay triangulation
of the point set when traversing all aspect ratios.
Algorithms for Labeling Focus Regions.
IEEE Transactions on Visualization and Computer Graphics, 18(12):25832592, 2012.
Martin Fink, JanHenrik Haunert, André Schulz, Joachim Spoerhase and Alexander Wolff.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
In this paper, we investigate the problem of labeling point sites in focus regions of maps or diagrams. This problem occurs, for example, when the user of a mapping service wants to see the names of restaurants or other POIs in a crowded downtown area but keep the overview over a larger area. Our approach is to place the labels at the boundary of the focus region and connect each site with its label by a linear connection, which is called a leader. In this way, we move labels from the focus region to the less valuable context region surrounding it. In order to make the leader layout well readable, we present algorithms that rule out crossings between leaders and optimize other characteristics such as total leader length and distance between labels. This yields a new variant of the boundary labeling problem, which has been studied in the literature. Other than in traditional boundary labeling, where leaders are usually schematized polylines, we focus on leaders that are either straightline segments or Bézier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics.
We also consider a variant of the problem where we have more sites than space for labels. In this situation, we assume that the sites are prioritized by the user. Alternatively, we take a new facilitylocation perspective which yields a clustering of the sites. We label one representative of each cluster. If the user wishes, we apply our approach to the sites within a cluster, giving details on demand.
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles.
In: M. v. Kreveld and B. Speckmann, editors,
Proc. 19th Int. Sympos. Graph Drawing (GD'11), volume 7034, series Lecture Notes in Computer Science, pages 441442.
SpringerVerlag, 2012.
Poster.
Martin Fink, JanHenrik Haunert, Tamara Mchedlidze, Joachim Spoerhase and Alexander Wolff.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
Pointset embeddings and largeangle crossings are two areas of graph drawing that independently have received a lot of attentionin the past few years. We consider problems in the intersection of these two areas. Given the pointsetembedding scenario, we are interested in how much we gain in terms of computational complexity, curve complexity, and generality if we allow largeangle crossings as compared to the planar case.
We investigate two drawing styles where only bends or both bends and edges must be drawn on an underlying grid. We present results for drawings with one, two, and three bends per edge.
Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles..
In: M. S. Rahman and S.i. Nakano, editors,
Proc. Workshop Algorithms Comput. (WALCOM'12), volume 7157, series Lecture Notes in Computer Science, pages 186197.
SpringerVerlag, 2012.
Martin Fink, JanHenrik Haunert, Tamara Mchedlidze, Joachim Spoerhase and Alexander Wolff.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
Pointset embeddings and largeangle crossings are two areas of graph drawing that independently have received a lot of attentionin the past few years. We consider problems in the intersection of these two areas. Given the pointsetembedding scenario, we are interested in how much we gain in terms of computational complexity, curve complexity, and generality if we allow largeangle crossings as compared to the planar case.
We investigate two drawing styles where only bends or both bends and edges must be drawn on an underlying grid. We present results for drawings with one, two, and three bends per edge.
Maximum Betweenness Centrality: Approximability and Tractable Cases.
In: N. Katoh and A. Kumar, editors,
Proc. Workshop Algorithms Comp. (WALCOM'11), volume 6552, series Lecture Notes in Computer Science, pages 920.
Springer, Berlin, Heidelberg, 2011.
Martin Fink and Joachim Spoerhase.
[doi] [pdf] [slides]
[abstract]
[BibTeX]
The Maximum Betweenness Centrality problem (MBC) can be defined as follows. Given a graph find a $k$element node set $C$ that maximizes the probability of detecting communication between a pair of nodes $s$ and $t$ chosen uniformly at random. It is assumed that the communication between $s$ and $t$ is realized along a shortest $s$$t$ path which is, again, selected uniformly at random. The communication is detected if the communication path contains a node of $C$.
Recently, Dolev et al. (2009) showed that MBC is NPhard and gave a $(11/e)$approximation using a greedy approach. We provide a reduction of MBC to Maximum Coverage that simplifies the analysis of the algorithm of Dolev et al. considerably. Our reduction allows us to obtain a new algorithm with the same approximation ratio for a (generalized) budgeted version of MBC. We provide tight examples showing that the analyses of both algorithms are best possible. Moreover, we prove that MBC is APXcomplete and provide an exact polynomialtime algorithm for MBC on tree graphs.
Zentralitätsmaße in komplexen Netzwerken auf Basis kürzester Wege.
Master's thesis (Diplomarbeit), Lehrstuhl für Informatik I, Universität Würzburg, 2009.
Martin Fink.
[pdf]
[BibTeX]