The optimal path between two vertices in a graph depends on the optimization objective, which is often defined as a weighted sum of multiple criteria. When integrating two criteria, their relative importance is expressed with a balance factor α. We present a new approach for inferring α from trajectories. The core of our approach is a compression algorithm that requires a graph G representing a transportation network, two edge costs modeling routing criteria, and a path P in G representing the trajectory. It yields a minimum subsequence S of the sequence of vertices of P and a balance factor α, such that the path P can be fully reconstructed from S, G, its edge costs, and α. By minimizing the size of S over α, we learn the balance factor that corresponds best to the user's routing preferences. In an evaluation with crowd-sourced cycling trajectories, we weigh the usage of official signposted cycle routes against other routes. More than 50% of the trajectories can be segmented into five optimal sub-paths or less. Almost 40% of the trajectories indicate that the cyclist is willing to take a detour of 50% over the geodesic shortest path to use an official cycle path.

doi:10.5311/JOSIS.2023.26.256

@article{forsch2023inferring,
    abstract = {The optimal path between two vertices in a graph depends on the optimization objective, which is often defined as a weighted sum of multiple criteria. When integrating two criteria, their relative importance is expressed with a balance factor α. We present a new approach for inferring α from trajectories. The core of our approach is a compression algorithm that requires a graph G representing a transportation network, two edge costs modeling routing criteria, and a path P in G representing the trajectory. It yields a minimum subsequence S of the sequence of vertices of P and a balance factor α, such that the path P can be fully reconstructed from S, G, its edge costs, and α. By minimizing the size of S over α, we learn the balance factor that corresponds best to the user's routing preferences. In an evaluation with crowd-sourced cycling trajectories, we weigh the usage of official signposted cycle routes against other routes. More than 50% of the trajectories can be segmented into five optimal sub-paths or less. Almost 40% of the trajectories indicate that the cyclist is willing to take a detour of 50% over the geodesic shortest path to use an official cycle path.},
    author = {Axel Forsch and Johannes Oehrlein and Benjamin Niedermann and Jan-Henrik Haunert},
    doi = {10.5311/JOSIS.2023.26.256},
    journal = {Journal of Spatial Information Science},
    number = {5},
    pages = {99--124},
    title = {Inferring routing preferences from user-generated trajectories using a compression criterion},
    volume = {26},
    year = {2023}
}

Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons.

doi:https://doi.org/10.1016/j.comgeo.2023.101983

@article{BONERATH2023101983,
    abstract = {Let P be a polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another polygon that encloses P and whose oriented boundary is composed of elements from C. We require P and the output shortcut hull to be weakly simple polygons, which we define as a generalization of simple polygons. Shortcut hulls find their application in cartography, where a common task is to compute simplified representations of area features. We aim at a shortcut hull that has a small area and a small perimeter. Our optimization objective is to minimize a convex combination of these two criteria. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via computation of shortest paths. For the more challenging case in which the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon's exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for the schematization of polygons.},
    author = {Annika Bonerath and Jan-Henrik Haunert and Joseph S.B. Mitchell and Benjamin Niedermann},
    doi = {https://doi.org/10.1016/j.comgeo.2023.101983},
    issn = {0925-7721},
    journal = {Computational Geometry Theory and Applications},
    pages = {101983},
    title = {Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons},
    url = {https://www.sciencedirect.com/science/article/pii/S0925772123000032},
    year = {2023}
}

This article addresses the augmentation of existing building models by a-priori not observable structures such as electric installations. The aim is to unambiguously determine an electric network in an incremental manner with a minimum number of local measurements, e.g. using wire detectors, by suggesting the next measurement. Different reasoning strategies, e.g. utilizing graph-theoretical algorithms, have been presented and tested based on a hypothesis which is generated using Mixed Integer Linear Programming (MILP) while incorporating standards regarding the installation of electric wiring and findings from previous measurements. The presented method has been successfully applied on simulated and real-world buildings, it saves up to 80% of the necessary measurements compared to an exhaustive verification of the whole existing electric network, and paves the way for efficiently extending existing models, e.g. GIS models, with information on hidden utilities. This opens up new opportunities to model further infrastructures, e.g. water pipes, in future research.

doi:10.1016/j.autcon.2022.104571

@article{dehbi2022incrementalConstraint-based,
    abstract = {This article addresses the augmentation of existing building models by a-priori not observable structures such as electric installations. The aim is to unambiguously
determine an electric network in an incremental manner with a minimum number of local measurements, e.g. using wire detectors, by suggesting the next measurement.
Different reasoning strategies, e.g. utilizing graph-theoretical algorithms, have been presented and tested based on a hypothesis which is generated using Mixed Integer
Linear Programming (MILP) while incorporating standards regarding the installation of electric wiring and findings from previous measurements. The presented
method has been successfully applied on simulated and real-world buildings, it saves up to 80% of the necessary measurements compared to an exhaustive verification
of the whole existing electric network, and paves the way for efficiently extending existing models, e.g. GIS models, with information on hidden utilities. This opens
up new opportunities to model further infrastructures, e.g. water pipes, in future research.},
    author = {Dehbi, Youness and Knechtel, Julius and Niedermann, Benjamin and Haunert, Jan-Henrik},
    doi = {10.1016/j.autcon.2022.104571},
    journal = {Automation in Construction},
    pages = {104571},
    title = {Incremental Constraint-based Reasoning for Estimating As-built Electric Line Routing in Buildings},
    volume = {143},
    year = {2022}
}

Let P be a crossing-free polygon and C a set of shortcuts, where each shortcut is a directed straight-line segment connecting two vertices of P. A shortcut hull of P is another crossing-free polygon that encloses P and whose oriented boundary is composed of elements from C. Shortcut hulls find their application in geo-related problems such as the simplification of contour lines. We aim at a shortcut hull that linearly balances the enclosed area and perimeter. If no holes in the shortcut hull are allowed, the problem admits a straight-forward solution via shortest paths. For the more challenging case that the shortcut hull may contain holes, we present a polynomial-time algorithm that is based on computing a constrained, weighted triangulation of the input polygon’s exterior. We use this problem as a starting point for investigating further variants, e.g., restricting the number of edges or bends. We demonstrate that shortcut hulls can be used for drawing the rough extent of point sets as well as for the schematization of polygons.

@inproceedings{Haunert2021,
    abstract = {Let P be a crossing-free polygon and C a set of shortcuts,
where each shortcut is a directed straight-line segment
connecting two vertices of P. A shortcut hull of
P is another crossing-free polygon that encloses P and
whose oriented boundary is composed of elements from
C. Shortcut hulls find their application in geo-related
problems such as the simplification of contour lines. We
aim at a shortcut hull that linearly balances the enclosed
area and perimeter. If no holes in the shortcut hull
are allowed, the problem admits a straight-forward solution
via shortest paths. For the more challenging case
that the shortcut hull may contain holes, we present a
polynomial-time algorithm that is based on computing
a constrained, weighted triangulation of the input polygon’s
exterior. We use this problem as a starting point
for investigating further variants, e.g., restricting the
number of edges or bends. We demonstrate that shortcut
hulls can be used for drawing the rough extent of
point sets as well as for the schematization of polygons.},
    author = {Annika Bonerath and Jan-Henrik Haunert and Joseph S. B. Mitchell and Benjamin Niedermann},
    booktitle = {Proceedings of the 33rd Canadian Conference on Computational Geometry},
    editor = {Meng He and Don Sheehy},
    pages = {12-23},
    title = {Shortcut Hulls: Vertex-restricted Outer Simplifications of Polygons},
    url = {https://projects.cs.dal.ca/cccg2021/wordpress/wp-content/uploads/2021/08/CCCG2021.pdf},
    year = {2021}
}

Visualizing spatial data on small-screen devices such as smartphones and smartwatches poses new challenges in computational cartography. The current interfaces for map exploration require their users to zoom in and out frequently. Indeed, zooming and panning are tools suitable for choosing the map extent corresponding to an area of interest. They are not as suitable, however, for resolving the graphical clutter caused by a high feature density since zooming in to a large map scale leads to a loss of context. Therefore, in this paper, we present new external labeling methods that allow a user to navigate through dense sets of points of interest while keeping the current map extent fixed. We provide a unified model, in which labels are placed at the boundary of the map and visually associated with the corresponding features via connecting lines, which are called leaders. Since the screen space is limited, labeling all features at the same time is impractical. Therefore, at any time, we label a subset of the features. We offer interaction techniques to change the current selection of features systematically and, thus, give the user access to all features. We distinguish three methods, which allow the user either to slide the labels along the bottom side of the map or to browse the labels based on pages or stacks. We present a generic algorithmic framework that provides us with the possibility of expressing the different variants of interaction techniques as optimization problems in a unified way. We propose both exact algorithms and fast and simple heuristics that solve the optimization problems taking into account different criteria such as the ranking of the labels, the total leader length as well as the distance between leaders. In experiments on real-world data we evaluate these algorithms and discuss the three variants with respect to their strengths and weaknesses proving the flexibility of the presented algorithmic framework.

doi:10.1109/TVCG.2020.3030399

@article{gbnh-zm-21,
    abstract = {Visualizing spatial data on small-screen devices such as
smartphones and smartwatches poses new challenges in computational
cartography. The current interfaces for map exploration require
their users to zoom in and out frequently. Indeed, zooming and
panning are tools suitable for choosing the map extent corresponding
to an area of interest. They are not as suitable, however, for
resolving the graphical clutter caused by a high feature
density since zooming in to a large map scale leads to a loss of
context. Therefore, in this paper, we present new external labeling methods that allow a user to navigate through dense sets of
points of interest while keeping the current map extent fixed. We provide a unified model, in which labels are
placed at the boundary of the map and visually associated with the
corresponding features via connecting lines, which are called
leaders. Since the screen space is limited, labeling all features
at the same time is impractical. Therefore, at any time, we label a
subset of the features. We offer interaction techniques to change
the current selection of features systematically and, thus, give the
user access to all features. We distinguish three methods, which
allow the user either to slide the labels along the bottom side of the map or
to browse the labels based on pages or stacks. We present a generic
algorithmic framework that provides us with the possibility of
expressing the different variants of interaction techniques as
optimization problems in a unified way. We propose both exact
algorithms and fast and simple heuristics that solve the
optimization problems taking into account different criteria such as
the ranking of the labels, the total leader length as well as the
distance between leaders. In experiments on real-world data we
evaluate these algorithms and discuss the three variants with
respect to their strengths and weaknesses proving the flexibility of
the presented algorithmic framework.},
    author = {Gedicke, Sven and Bonerath, Annika and Niedermann, Benjamin and Haunert, Jan-Henrik},
    doi = {10.1109/TVCG.2020.3030399},
    journal = {IEEE Transactions on Visualization and Computer Graphics},
    note = {https://youtu.be/IuMhk8jp54c},
    number = {2},
    pages = {1247--1256},
    title = {{Z}oomless {M}aps: {E}xternal {L}abeling {M}ethods for the {I}nteractive {E}xploration of {D}ense {P}oint {S}ets at a {F}ixed {M}ap {S}cale},
    volume = {27},
    year = {2021}
}

The automatic generation of travel-time maps is a prerequisite for many fields of application such as tourist assistance and spatial decision support systems. The task is to determine outlines of zones that are reachable from a user's location in a given amount of time. In this work, we focus on travel-time maps with a formally guaranteed separation property in the sense that a zone exactly contains the part of the road network that is reachable within a pre-defined time from a given starting point and start time. In contrast to other automated methods, our approach generates schematized travel-time maps that reduce the visual complexity by representing each zone by an octilinear polygon. We aim at octilinear polygons with a small number of bends to further optimize the legibility of the map. The reachable parts of the road network are determined by the integration of timetable information for different modes of public transportation and pedestrian walkways based on a multi-modal time-expanded network. Moreover, the generated travel-time maps visualize multiple travel times using a map overlay of different time zones. In experiments on real-world data we compare our schematic visualizations to travel-time maps created with other visualization techniques.

doi:10.1111/tgis.12821

@article{forsch2021isochrones,
    abstract = {The automatic generation of travel-time maps is a prerequisite for many fields of application such as tourist assistance and spatial decision support systems. The task is to determine outlines of zones that are reachable from a user's location in a given amount of time. In this work, we focus on travel-time maps with a formally guaranteed separation property in the sense that a zone exactly contains the part of the road network that is reachable within a pre-defined time from a given starting point and start time. In contrast to other automated methods, our approach generates schematized travel-time maps that reduce the visual complexity by representing each zone by an octilinear polygon. We aim at octilinear polygons with a small number of bends to further optimize the legibility of the map. The reachable parts of the road network are determined by the integration of timetable information for different modes of public transportation and pedestrian walkways based on a multi-modal time-expanded network. Moreover, the generated travel-time maps visualize multiple travel times using a map overlay of different time zones. In experiments on real-world data we compare our schematic visualizations to travel-time maps created with other visualization techniques.},
    author = {Forsch, Axel and Dehbi, Youness and Niedermann, Benjamin and Oehrlein, Johannes and Rottmann, Peter and Haunert, Jan-Henrik},
    doi = {10.1111/tgis.12821},
    journal = {Transactions in GIS},
    number = {6},
    pages = {3233--3256},
    title = {Multimodal Travel-Time Maps with Formally Correct and Schematic Isochrones},
    volume = {25},
    year = {2021}
}

Map applications on mobile devices such as smartphones and smartwatches have become ubiquitous. When visualizing spatial data on such small-screen devices, one major challenge is annotating the data with labels (e.g., small icons). The restricted space requires new visualization techniques as established strategies, such as maximizing the number of placed labels, easily lead to the omission of information. We propose an approach that distributes all labels contained in a temporarily fixed map section on multiple pages. Applying interaction techniques for navigating through the pages, a user can access all information both without any overlapping labels and without the need for zooming. We propose a method with two phases; a pre-processing phase and a query phase. We use an optimization approach to pre-compute labelings on the level of a whole city and provide the on-demand querying of individual labelings at a more local level. Our approach provides a consistent label-page assignment, meaning that labels do not appear and disappear when the user pans the map. Further, our model provides quick access to important information and a spatially balanced distribution of labels on pages. In experiments on real-world data we analyze different parameter settings and show that our model yields high-quality labelings.

doi:10.1016/j.cag.2021.07.019

@article{gjnmh-zm-21,
    abstract = {Map applications on mobile devices such as smartphones and smartwatches have become ubiquitous. When visualizing spatial data on such small-screen devices, one major challenge is annotating the data with labels (e.g., small icons). The restricted space requires new visualization techniques as established strategies, such as maximizing the number of placed labels, easily lead to the omission of information. We propose an approach that distributes all labels contained in a temporarily fixed map section on multiple pages. Applying interaction techniques for navigating through the pages, a user can access all information both without any overlapping labels and without the need for zooming. We propose a method with two phases; a pre-processing phase and a query phase. We use an optimization approach to pre-compute labelings on the level of a whole city and provide the on-demand querying of individual labelings at a more local level. Our approach provides a consistent label-page assignment, meaning that labels do not appear and disappear when the user pans the map. Further, our model provides quick access to important information and a spatially balanced distribution of labels on pages. In experiments on real-world data we analyze different parameter settings and show that our model yields high-quality labelings.},
    author = {Gedicke, S. and Jabrayilov, A. and Niedermann, B. and Mutzel, P. and Haunert, J.-H.},
    doi = {10.1016/j.cag.2021.07.019},
    issn = {0097-8493},
    journal = {Computers & Graphics},
    pages = {66-80},
    title = {Point feature label placement for multi-page maps on small-screen devices},
    url = {https://www.sciencedirect.com/science/article/pii/S0097849321001564},
    volume = {100},
    year = {2021}
}

The visualization of spatio-temporal data helps researchers understand global processes such as animal migration. In particular, interactively restricting the data to different time windows reveals new insights into the short-term and long-term changes of the research data. Inspired by this use case, we consider the visualization of point data annotated with time stamps. We pick up classical, grid-based density maps as the underlying visualization technique and enhance them with an efficient data structure for arbitrarily specified time-window queries. The running time of the queries is logarithmic in the total number of points and linear in the number of actually colored cells. In experiments on real-world data we show that the data structure answers time-window queries within milliseconds, which supports the interactive exploration of large point sets. Further, the data structure can be used to visualize additional decision problems, e.g., it can answer whether the sum or maximum of additional weights given with the points exceed a certain threshold. We have defined the data structure general enough to also support multiple thresholds expressed by different colors.

doi:10.1145/3397536.3422242

@inproceedings{bhn-twdssdm-20,
    abstract = {The visualization of spatio-temporal data helps researchers
understand global processes such as animal migration. In particular,
interactively restricting the data to different time windows reveals
new insights into the short-term and long-term changes of the
research data. Inspired by this use case, we consider the
visualization of point data annotated with time stamps. We pick up
classical, grid-based density maps as the underlying visualization
technique and enhance them with an efficient data structure for
arbitrarily specified time-window queries. The running time of the
queries is logarithmic in the total number of points and linear in
the number of actually colored cells. In experiments on real-world
data we show that the data structure answers time-window queries
within milliseconds, which supports the interactive exploration of large
point sets. Further, the data structure can be used to visualize
additional decision problems, e.g., it can answer whether
the sum or maximum of additional weights given with the points
exceed a certain threshold. We have defined the data structure
general enough to also support multiple thresholds expressed by
different colors.},
    author = {Bonerath, A. and Niedermann, B. and Diederich, J. and Orgeig, Y. and Oehrlein, J. and Haunert, J.-H.},
    booktitle = {Proc. 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20)},
    doi = {10.1145/3397536.3422242},
    pages = {15--24},
    title = {{A Time-Windowed Data Structure for Spatial Density Maps}},
    year = {2020}
}

An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.

@inproceedings{nr-ilpbmord2020,
    abstract = {An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.},
    author = {B. Niedermann and I. Rutter},
    booktitle = {Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD'20)},
    editor = {Auber, David and Valtr, Pavel},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings}},
    year = {2020}
}

Transit maps are designed to present information for using public transportation systems, such as urban railways. Creating a transit map is a time-consuming process, which requires iterative information selection, layout design, and usability validation, and thus maps cannot easily be customised or updated frequently. To improve this, scientists investigate fully- or semi-automatic techniques in order to produce high quality transit maps using computers and further examine their corresponding usability. Nonetheless, the quality gap between manually-drawn maps and machine-generated maps is still large. To elaborate the current research status, this state-of-the-art report provides an overview of the transit map generation process, primarily from Design, Machine, and Human perspectives. A systematic categorisation is introduced to describe the design pipeline, and an extensive analysis of perspectives is conducted to support the proposed taxonomy. We conclude this survey with a discussion on the current research status, open challenges, and future directions.

doi:10.1111/cgf.14030

@article{wntrn-stlfdmhp-20,
    abstract = {Transit maps are designed to present information for using public transportation systems, such as urban railways. Creating a transit map is a time-consuming process, which requires iterative information selection, layout design, and usability validation, and thus maps cannot easily be customised or updated frequently. To improve this, scientists investigate fully- or semi-automatic techniques in order to produce high quality transit maps using computers and further examine their corresponding usability. Nonetheless, the quality gap between manually-drawn maps and machine-generated maps is still large. To elaborate the current research status, this state-of-the-art report provides an overview of the transit map generation process, primarily from Design, Machine, and Human perspectives. A systematic categorisation is introduced to describe the design pipeline, and an extensive analysis of perspectives is conducted to support the proposed taxonomy. We conclude this survey with a discussion on the current research status, open challenges, and future directions.},
    author = {Wu, H.-Y. and Niedermann, B. and Takahashi, S. and Roberts, M. J. and Nöllenburg, M.},
    doi = {10.1111/cgf.14030},
    journal = {Computer Graphics Forum},
    number = {3},
    title = {A Survey on Transit Map Layout -- from Design, Machine, and Human Perspectives},
    url = {https://diglib.eg.org/bitstream/handle/10.1111/cgf14030/v39i3pp619-646.pdf},
    volume = {39},
    year = {2020}
}

We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels’ presences, activities and conflicts. One of the model’s strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is NP-complete and W[1]-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than k labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms.

doi:10.1007/s00453-020-00694-7

@article{gnn-umatml20,
    abstract = {We consider map labeling for the case that a map undergoes a sequence of operations such as rotation, zoom and translation over a specified time span. We unify and generalize several previous models for dynamic map labeling into one versatile and flexible model. In contrast to previous research, we completely abstract from the particular operations and express the labeling problem as a set of time intervals representing the labels’ presences, activities and conflicts. One of the model’s strength is manifested in its simplicity and broad range of applications. In particular, it supports label selection both for map features with fixed position as well as for moving entities (e.g., for tracking vehicles in logistics or air traffic control). We study the active range maximization problem in this model. We prove that the problem is NP-complete and W[1]-hard, and present constant-factor approximation algorithms. In the restricted, yet practically relevant case that no more than k labels can be active at any time, we give polynomial-time algorithms as well as constant-factor approximation algorithms.},
    author = {Gemsa, A. and Niedermann, B. and Nöllenburg, M.},
    doi = {10.1007/s00453-020-00694-7},
    journal = {Algorithmica},
    pages = {2702--2736},
    title = {A Unified Model and Algorithms for Temporal Map Labeling},
    volume = {82},
    year = {2020}
}

A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C. The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints. We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.

@inproceedings{bhn-trhsp-20,
    abstract = {A polygon is called C-oriented if the orientations of all its edges stem from a pre-defined set C.
The schematization of a polygon is then a C-oriented polygon that describes and simplifies the shape of the input polygon with respect to given hard and soft constraints.
We study the case that the C-oriented polygon needs to contain the input polygon such that it is tight in the sense that it cannot be shrunk without starting to overlap
with the input polygon; we call this a tight C-hull of the polygon. We restrict the tight C-hull to be a simple polygon. We aim at a tight C-hull that optimally balances
the number of bends, the total edge length and the enclosed area. For the case that both polygons are rectilinear, we present a dynamic-programming approach that yields
such a tight hull in polynomial time. For arbitrary simple polygons we can use the same approach to obtain approximate tight rectilinear hulls.},
    author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
    booktitle = {Proceedings of the 36th European Workshop on Computational Geometry (EuroCG'20)},
    note = {trailer: https://youtu.be/GZTS5fs0FG4, presentation: https://youtu.be/B392e75WK2U},
    title = {{Tight Rectilinear Hulls of Simple Polygons}},
    url = {http://www1.pub.informatik.uni-wuerzburg.de/eurocg2020/data/uploads/eurocg20_proceedings.pdf},
    year = {2020}
}

In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.

@inproceedings{bhn-dagoierd20,
    abstract = {In the context of research data management, the interactive exploration of data is a useful tool to make data findable and reusable. For exploring spatio- and temporal data we developed in a previously published work a data structure that provides the user with simple visualizations of the data for time window queries. We considered the data to be points in space each associated with a time stamp and we visualized it using \alpha-shapes, which generalize convex hulls. In general, time windowed data structures support time window queries for geometric shapes or more general problems from computational geometry such as counting and intersection problems. With this paper, we contribute a review of our previously published method in the context of time windowed data structures, which is a relatively new concept of computational geometry. In particular, we highlight the relevance of our work for a growing domain of research.},
    author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
    booktitle = {Publikationen der Deutschen Gesellschaft f\"ur Photogrammetrie, Fernerkundung und Geoinformation e.V., DGPF Jahrestagung 2020, Stuttgart, Germany},
    number = {0},
    pages = {488--496},
    title = {Dynamic Aggregation of Geo-Objects for the Interactive Exploration of Research Data},
    volume = {29},
    year = {2020}
}

A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in cubic running time if the road map is an embedded tree with n vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps.

doi:10.1007/s00453-020-00678-7

@article{gnn-plrmac20,
    abstract = {A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in cubic running time if the road map is an embedded tree with n vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps.},
    author = {Gemsa, A. and Niedermann, B. and Nöllenburg, M.},
    doi = {10.1007/s00453-020-00678-7},
    journal = {Algorithmica},
    note = {Online first.},
    number = {0},
    pages = {1--28},
    title = {Placing Labels in Road Maps: Algorithms and Complexity},
    volume = {0},
    year = {2020}
}

Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes.

doi:10.1007/s00190-020-01348-w

@article{cnnhh-coas20,
    abstract = {Due to the advent of powerful solvers, today linear programming has seen many applications in production and routing. In this publication, we present mixed-integer linear programming as applied to scheduling geodetic very-long-baseline interferometry (VLBI) observations. The approach uses combinatorial optimization and formulates the scheduling task as a mixed-integer linear program. Within this new method, the schedule is considered as an entity containing all possible observations of an observing session at the same time, leading to a global optimum. In our example, the optimum is found by maximizing the sky coverage score. The sky coverage score is computed by a hierarchical partitioning of the local sky above each telescope into a number of cells. Each cell including at least one observation adds a certain gain to the score. The method is computationally expensive and this publication may be ahead of its time for large networks and large numbers of VLBI observations. However, considering that developments of solvers for combinatorial optimization are progressing rapidly and that computers increase in performance, the usefulness of this approach may come up again in some distant future. Nevertheless, readers may be prompted to look into these optimization methods already today seeing that they are available also in the geodetic literature. The validity of the concept and the applicability of the logic are demonstrated by evaluating test schedules for five 1-h, single-baseline Intensive VLBI sessions. Compared to schedules that were produced with the scheduling software sked, the number of observations per session is increased on average by three observations and the simulated precision of UT1-UTC is improved in four out of five cases (6 µs average improvement in quadrature). Moreover, a simplified and thus much faster version of the mixed-integer linear program has been developed for modern VLBI Global Observing System telescopes.},
    author = {Corbin, A. and Niedermann, B. and Nothnagel, A. and Haas R. and Haunert, J.-H.},
    doi = {10.1007/s00190-020-01348-w},
    journal = {Journal of Geodesy},
    number = {19},
    pages = {1--22},
    title = {Combinatorial optimization applied to {VLBI} scheduling},
    volume = {94},
    year = {2020}
}

Abstract External labeling is frequently used for annotating features in graphical displays and visualizations, such as technical illustrations, anatomical drawings, or maps, with textual information. Such a labeling connects features within an illustration by thin leader lines with their labels, which are placed in the empty space surrounding the image. Over the last twenty years, a large body of literature in diverse areas of computer science has been published that investigates many different aspects, models, and algorithms for automatically placing external labels for a given set of features. This state-of-the-art report introduces a first unified taxonomy for categorizing the different results in the literature and then presents a comprehensive survey of the state of the art, a sketch of the most relevant algorithmic techniques for external labeling algorithms, as well as a list of open research challenges in this multidisciplinary research field.

doi:10.1111/cgf.13729

@article{doi:10.1111/cgf.13729,
    abstract = {Abstract External labeling is frequently used for annotating features in graphical displays and visualizations, such as technical illustrations, anatomical drawings, or maps, with textual information. Such a labeling connects features within an illustration by thin leader lines with their labels, which are placed in the empty space surrounding the image. Over the last twenty years, a large body of literature in diverse areas of computer science has been published that investigates many different aspects, models, and algorithms for automatically placing external labels for a given set of features. This state-of-the-art report introduces a first unified taxonomy for categorizing the different results in the literature and then presents a comprehensive survey of the state of the art, a sketch of the most relevant algorithmic techniques for external labeling algorithms, as well as a list of open research challenges in this multidisciplinary research field.},
    author = {Bekos, M. and Niedermann, B. and Nöllenburg, M.},
    doi = {10.1111/cgf.13729},
    eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1111/cgf.13729},
    journal = {Computer Graphics Forum},
    number = {3},
    pages = {833--860},
    title = {External Labeling Techniques: A Taxonomy and Survey},
    url = {https://onlinelibrary.wiley.com/doi/abs/10.1111/cgf.13729},
    volume = {38},
    year = {2019}
}

Zooming is a basic operation that many digital maps support for exploring them interactively. Especially for maps on small-screen devices this is a helpful operation to uncover the user’s region of interest possibly hidden by labels, e.g., points of interest represented by icons. However, by scaling the map larger the user loses the context. As a consequent the user might need to repeatedly zoom in and out to explore the map step by step. We present an approach that reduces the necessity of zooming by providing the user with the possibility of displacing the labels of a circular focus region. To that end, we utilize techniques from focus+context maps implementing the displacement of the labels by fish-eye projections. The visual association between labels and their point features is established by connecting lines aggregated to bundles. Our approach particularly guarantees that labels move smoothly when the user continuously shifts the focus region, which reduces distracting flickering effects while exploring the map by panning the map view. Further, when the user stops moving the focus region, mathematical programming is applied to optimize positions of the displaced labels. In an evaluation on real-world data and synthetically generated data we show that our approach substantially increases the legibility of both the focus region and the displaced labels

doi:10.1080/23729333.2019.1613072

@article{niedermann2019,
    abstract = {Zooming is a basic operation that many digital maps support for exploring them interactively. Especially
for maps on small-screen devices this is a helpful operation to uncover the user’s region of interest possibly hidden by
labels, e.g., points of interest represented by icons. However, by scaling the map larger the user loses the context. As a
consequent the user might need to repeatedly zoom in and out to explore the map step by step.
We present an approach that reduces the necessity of zooming by providing the user with the possibility of displacing
the labels of a circular focus region. To that end, we utilize techniques from focus+context maps implementing the
displacement of the labels by fish-eye projections. The visual association between labels and their point features is
established by connecting lines aggregated to bundles. Our approach particularly guarantees that labels move smoothly
when the user continuously shifts the focus region, which reduces distracting flickering effects while exploring the map
by panning the map view. Further, when the user stops moving the focus region, mathematical programming is applied to
optimize positions of the displaced labels. In an evaluation on real-world data and synthetically generated data we show
that our approach substantially increases the legibility of both the focus region and the displaced labels},
    author = {Niedermann, B. and Haunert, J.{-}H.},
    doi = {10.1080/23729333.2019.1613072},
    journal = {International Journal of Cartography},
    note = {Special issue of 29th International Cartographic Conference (ICC'19)},
    number = {2--3},
    pages = {158--177},
    publisher = {Taylor & Francis},
    title = {Focus+Context Map Labeling with Optimized Clutter Reduction},
    volume = {5},
    year = {2019}
}

Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing. Often the goal is to find a drawing that minimizes the number of bends on the edges. A key ingredient for bend minimization algorithms is the existence of an orthogonal representation that allows to describe such drawings purely combinatorially by only listing the angles between the edges around each vertex and the directions of bends on the edges, but neglecting any kind of geometric information such as vertex coordinates or edge lengths. Barth et al. have established the existence of an analogous ortho-radial representation for ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric circles around the origin and straight-line spokes emanating from the origin but excluding the origin itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all the more complex and interesting. Barth et al. prove such a characterization. However, the proof is existential and does not provide an efficient algorithm for testing whether a given ortho-radial representation is valid, let alone actually obtaining a drawing from an ortho-radial representation. In this paper we give quadratic-time algorithms for both of these tasks. They are based on a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial representations. Our validity check requires quadratic time, and a naive application of it would yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation

doi:10.4230/LIPIcs.SoCG.2019.53

@inproceedings{nrw-eaorgd-19,
    abstract = {Orthogonal drawings, i.e., embeddings of graphs into grids, are a classic topic in Graph Drawing.
Often the goal is to find a drawing that minimizes the number of bends on the edges. A key
ingredient for bend minimization algorithms is the existence of an orthogonal representation that
allows to describe such drawings purely combinatorially by only listing the angles between the edges
around each vertex and the directions of bends on the edges, but neglecting any kind of geometric
information such as vertex coordinates or edge lengths.
Barth et al. have established the existence of an analogous ortho-radial representation for
ortho-radial drawings, which are embeddings into an ortho-radial grid, whose gridlines are concentric
circles around the origin and straight-line spokes emanating from the origin but excluding the origin
itself. While any orthogonal representation admits an orthogonal drawing, it is the circularity of
the ortho-radial grid that makes the problem of characterizing valid ortho-radial representations all
the more complex and interesting. Barth et al. prove such a characterization. However, the proof
is existential and does not provide an efficient algorithm for testing whether a given ortho-radial
representation is valid, let alone actually obtaining a drawing from an ortho-radial representation.
In this paper we give quadratic-time algorithms for both of these tasks. They are based on
a suitably constrained left-first DFS in planar graphs and several new insights on ortho-radial
representations. Our validity check requires quadratic time, and a naive application of it would
yield a quartic algorithm for constructing a drawing from a valid ortho-radial representation},
    author = {Niedermann, B. and Rutter, I. and Wolf, M.},
    booktitle = {Proc. 35th Annual ACM Symposium on Computational Geometry (SoCG '19)},
    doi = {10.4230/LIPIcs.SoCG.2019.53},
    publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
    series = {Leibniz International Proceedings in Informatics},
    title = {{Efficient Algorithms for Ortho-Radial Graph Drawing}},
    volume = {129},
    year = {2019}
}

External labeling deals with annotating features in images with labels that are placed outside of the image and are connected by curves (so-called leaders) to the corresponding features. While external labeling has been extensively investigated from a perspective of automatization, the research on its readability has been neglected. In this article, we present the first formal user study on the readability of leader types in boundary labeling, a special variant of external labeling that considers rectangular image contours. We consider the four most studied leader types (straight, L-shaped, diagonal, and S-shaped) with respect to their performance, that is, whether and how fast a viewer can assign a feature to its label and vice versa. We give a detailed analysis of the results regarding the readability of the four models and discuss their aesthetic qualities based on the users’ preference judgments and interviews. As a consequence of our experiment, we can generally recommend L-shaped leaders as the best compromise between measured task performance and subjective preference ratings, while straight and diagonal leaders received mixed ratings in the two measures. S-shaped leaders are generally not recommended from a practical point of view.

doi:10.1177/1473871618799500

@article{doi:10.1177/1473871618799500,
    abstract = {External labeling deals with annotating features in images with labels that are placed outside of the image and are connected by curves (so-called leaders) to the corresponding features. While external labeling has been extensively investigated from a perspective of automatization, the research on its readability has been neglected. In this article, we present the first formal user study on the readability of leader types in boundary labeling, a special variant of external labeling that considers rectangular image contours. We consider the four most studied leader types (straight, L-shaped, diagonal, and S-shaped) with respect to their performance, that is, whether and how fast a viewer can assign a feature to its label and vice versa. We give a detailed analysis of the results regarding the readability of the four models and discuss their aesthetic qualities based on the users’ preference judgments and interviews. As a consequence of our experiment, we can generally recommend L-shaped leaders as the best compromise between measured task performance and subjective preference ratings, while straight and diagonal leaders received mixed ratings in the two measures. S-shaped leaders are generally not recommended from a practical point of view.},
    author = {Barth, L. and Gemsa, A. and Niedermann, B. and Nöllenburg, M.},
    doi = {10.1177/1473871618799500},
    journal = {Information Visualization},
    number = {1},
    pages = {110-132},
    title = {On the readability of leaders in boundary labeling},
    volume = {18},
    year = {2019}
}

The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. In this paper we consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data.

@inproceedings{bhn-castrqps-19,
    abstract = {The interactive exploration of data requires data structures that can be repeatedly queried to
obtain simple visualizations of parts of the data. In this paper we consider the scenario that the
data is a set of points each associated with a time stamp and that the result of each query is
visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing
each shape independently, we suggest and analyze a simple data structure that aggregates the
α-shapes of all possible queries. Once the data structure is built, it particularly allows us to
query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly
produce small previews of the queried data.},
    author = {Bonerath, A. and Haunert, J.-H. and Niedermann, B.},
    booktitle = {Proceedings of the 35rd European Workshop on Computational Geometry (EuroCG'19)},
    note = {Preprint.},
    title = {{Computing alpha-Shapes for Temporal Range Queries on Point Sets}},
    year = {2019}
}

For conducting navigation tasks in public trans- portation systems, schematic maps (e.g., metro maps) are the first choice, as they reduce the amount of information to a minimum. On the other hand, for navigation tasks in street networks, classical geographic maps are preferable, as they depict the area as accurately as possible. In this work, we create synergies between both types of maps by laying the metro map over the street map. We call those maps anchored metro maps, as we visually attach the metro stations of the metro map to their counterparts on the street map. Currently, we are developing algorithms optimizing the matching between both maps. In future research we plan to use this approach to show that the combination of schematic and geographical maps leads to an improvement for certain navigation tasks.

@inproceedings{nh-amm-19,
    abstract = {For conducting navigation tasks in public trans-
portation systems, schematic maps (e.g., metro maps) are the first
choice, as they reduce the amount of information to a minimum.
On the other hand, for navigation tasks in street networks,
classical geographic maps are preferable, as they depict the
area as accurately as possible. In this work, we create synergies
between both types of maps by laying the metro map over the
street map. We call those maps anchored metro maps, as we
visually attach the metro stations of the metro map to their
counterparts on the street map. Currently, we are developing
algorithms optimizing the matching between both maps. In
future research we plan to use this approach to show that the
combination of schematic and geographical maps leads to an
improvement for certain navigation tasks.},
    author = {Niedermann, B. and Haunert, J.-H.},
    booktitle = {Schematic Mapping Workshop 2019},
    note = {Poster abstract.},
    title = {Anchored Metro Maps: Combining Schematic Maps
with Geographic Maps for Multi-modal Navigation},
    year = {2019}
}

Schematic maps are in daily use to show the connectivity of subway systems and to facilitate travellers to plan their journeys effectively. This study surveys up-to-date algorithmic approaches in order to give an overview of the state of the art in schematic network mapping. The study investigates the hypothesis that the choice of algorithmic approach is often guided by the requirements of the mapping application. For example, an algorithm that computes globally optimal solutions for schematic maps is capable of producing results for printing, while it is not suitable for computing instant layouts due to its long running time. Our analysis and discussion, therefore, focus on the computational complexity of the problem formulation and the running times of the schematic map algorithms, including algorithmic network layout techniques and station labeling techniques. The correlation between problem complexity and running time is then visually depicted using scatter plot diagrams. Moreover, since metro maps are common metaphors for data visualization, we also investigate online tools and application domains using metro map representations for analytics purposes, and finally summarize the potential future opportunities for schematic maps.

@inproceedings{wntn-scsnm-19,
    abstract = {Schematic maps are in daily use to show the connectivity of subway systems and to facilitate travellers to plan their
journeys effectively. This study surveys up-to-date algorithmic
approaches in order to give an overview of the state of the
art in schematic network mapping. The study investigates the
hypothesis that the choice of algorithmic approach is often guided
by the requirements of the mapping application. For example, an
algorithm that computes globally optimal solutions for schematic
maps is capable of producing results for printing, while it is not
suitable for computing instant layouts due to its long running
time. Our analysis and discussion, therefore, focus on the computational complexity of the problem formulation and the running
times of the schematic map algorithms, including algorithmic
network layout techniques and station labeling techniques. The
correlation between problem complexity and running time is
then visually depicted using scatter plot diagrams. Moreover,
since metro maps are common metaphors for data visualization,
we also investigate online tools and application domains using
metro map representations for analytics purposes, and finally
summarize the potential future opportunities for schematic maps.},
    author = {Wu, H.-Y. and Niedermann, B. and Takahashi, S. and Nöllenburg, M.},
    booktitle = {Schematic Mapping Workshop 2019},
    note = {Preprint.},
    title = {A Survey on Computing Schematic Network Maps: The Challenge to Interactivity},
    year = {2019}
}

The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.

doi:10.1145/3347146.3359087

@inproceedings{bhn-rasspa-19,
    abstract = {The interactive exploration of data requires data structures that can be repeatedly queried to obtain simple visualizations of parts of the data. We consider the scenario that the data is a set of points each associated with a time stamp and that the result of each query is visualized by an α-shape, which generalizes the concept of convex hulls. Instead of computing each shape independently, we suggest and analyze a simple data structure that aggregates the α-shapes of all possible queries. Once the data structure is built, it particularly allows us to query single α-shapes without retrieving the actual (possibly large) point set and thus to rapidly produce small previews of the queried data. We discuss the data structure for the original α-shapes as well as for a schematized version of α-shapes, which further simplifies the visualization. We evaluate the data structure on real-world data. The experiments indicate linear memory consumption with respect to the number of points, which makes the data structure applicable in practice, although the size is quadratic for a theoretic worst case example.},
    author = {Bonerath, A. and Niedermann, B. and Haunert, J.-H.},
    booktitle = {Proc. 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '19)},
    doi = {10.1145/3347146.3359087},
    note = {trailer: https://youtu.be/mlnUDhbMSfQ},
    pages = {249--258},
    title = {{Retrieving alpha-Shapes and Schematic Polygonal Approximations for Sets of Points within Queried Temporal Ranges}},
    year = {2019}
}

Annotating small-screen maps with additional content such as labels for points of interest is a highly challenging problem that requires new algorithmic solutions. A common labeling approach is to select a maximum-size subset of all labels such that no two labels constitute a graphical conflict and to display only the selected labels in the map. A disadvantage of this approach is that a user often has to zoom in and out repeatedly to access all points of interest in a certain region. Since this can be very cumbersome, we suggest an alternative approach that allows the scale of the map to be kept fixed. Our approach is to distribute all labels on multiple pages through which the user can navigate, for example, by swiping the pages from right to left. We in particular optimize the assignment of the labels to pages such that no page contains two conflicting labels, more important labels appear on the first pages, and sparsely labeled pages are avoided. Algorithmically, we reduce this problem to a weighted and constrained graph coloring problem based on a graph representing conflicts between labels such that an optimal coloring of the graph corresponds to a multi-page labeling. We propose a simple greedy heuristic that is fast enough to be deployed in web-applications. We evaluate the quality of the obtained labelings by comparing them with optimal solutions, which we obtain by means of integer linear programming formulations. In our evaluation on real-world data we particularly show that the proposed heuristic achieves near-optimal solutions with respect to the chosen objective function and that it substantially improves the legibility of the labels in comparison to the simple strategy of assigning the labels to pages solely based on the labels' weights.

@inproceedings{gedicke2019a,
    abstract = {Annotating small-screen maps with additional content such as labels for points of interest is a highly challenging problem that requires new algorithmic solutions. A common labeling approach is to select a maximum-size subset of all labels such that no two labels constitute a graphical conflict and to display only the selected labels in the map. A disadvantage of this approach is that a user often has to zoom in and out repeatedly to access all points of interest in a certain region. Since this can be very cumbersome, we suggest an alternative approach that allows the scale of the map to be kept fixed. Our approach is to distribute all labels on multiple pages through which the user can navigate, for example, by swiping the pages from right to left. We in particular optimize the assignment of the labels to pages such that no page contains two conflicting labels, more important labels appear on the first pages, and sparsely labeled pages are avoided.
Algorithmically, we reduce this problem to a weighted and constrained graph coloring problem based on a graph representing conflicts between labels such that an optimal coloring of the graph corresponds to a multi-page labeling. We propose a simple greedy heuristic that is fast enough to be deployed in web-applications. We evaluate the quality of the obtained labelings by comparing them with optimal solutions, which we obtain by means of integer linear programming formulations. In our evaluation on real-world data we particularly show that the proposed heuristic achieves near-optimal solutions with respect to the chosen objective function and that it substantially improves the legibility of the labels in comparison to the simple strategy of assigning the labels to pages solely based on the labels' weights.},
    author = {Gedicke, S. and Niedermann, B. and Haunert, J.-H.},
    booktitle = {LBS 2019: 15th International Conference on Location Based Services, November 11--13, 2019, Vienna, AT},
    title = {{M}ulti-page {L}abeling of {S}mall-screen {M}aps with a {G}raph-coloring {A}pproach},
    year = {2019}
}

Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of all green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns green spaces of a prescribed size exclusively to each resident, such that an objective function that, in particular, considers the average distance between residents and assigned green spaces is optimized. We contribute a detailed presentation on how to engineer an assignment-based method, such that it yields plausible results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130,000 polygons representing green spaces, 18,000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision-making.

doi:10.1007/s41064-019-00081-0

@article{oehrlein2019-pfg,
    abstract = {Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of all green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns green spaces of a prescribed size exclusively to each resident, such that an objective function that, in particular, considers the average distance between residents and assigned green spaces is optimized. We contribute a detailed presentation on how to engineer an assignment-based method, such that it yields plausible results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130,000 polygons representing green spaces, 18,000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision-making.},
    author = {Oehrlein, J. and Niedermann, B. and Haunert, J.-H.},
    doi = {10.1007/s41064-019-00081-0},
    journal = {Journal of Photogrammetry, Remote Sensing and Geoinformation Science (PFG)},
    number = {4},
    pages = {137--158},
    title = {Analyzing the Supply and Detecting Spatial Patterns of Urban Green Spaces via Optimization},
    volume = {87},
    year = {2019}
}

Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.

doi:10.1007/s00453-017-0350-0

@article{HaunertN15a,
    abstract = {Drawing network maps automatically comprises two challenging steps, namely laying out the map and placing non-overlapping labels. In this paper we tackle the problem of labeling an already existing network map considering the application of metro maps. We present a flexible and versatile labeling model. Despite its simplicity, we prove that it is NP-complete to label a single line of the network. For a restricted variant of that model, we introduce an efficient algorithm that optimally labels a single line. Based on that algorithm, we present a general and sophisticated workflow for multiple metro lines, which is experimentally evaluated on real-world metro maps.},
    author = {Niedermann, B. and Haunert, J.{-}H.},
    doi = {10.1007/s00453-017-0350-0},
    journal = {Algorithmica},
    number = {5},
    pages = {1493--1533},
    title = {An Algorithmic Framework for Labeling Network Maps},
    volume = {80},
    year = {2018}
}

Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns a green space of a prescribed size exclusively to each resident such that the average distance between residents and assigned green spaces is minimized. We contribute a detailed presentation on how to engineer an assignment-based method such that it yields reasonable results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130000 polygons representing green spaces, 18000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision making.

doi:10.4230/LIPIcs.GISCIENCE.2018.13

@inproceedings{NiedermannEtAl2018,
    abstract = {Green spaces in urban areas offer great possibilities of recreation, provided that they are easily accessible. Therefore, an ideal city should offer large green spaces close to where its residents live. Although there are several measures for the assessment of urban green spaces, the existing measures usually focus either on the total size of green spaces or on their accessibility. Hence, in this paper, we present a new methodology for assessing green-space provision and accessibility in an integrated way. The core of our methodology is an algorithm based on linear programming that computes an optimal assignment between residential areas and green spaces. In a basic setting, it assigns a green space of a prescribed size exclusively to each resident such that the average distance between residents and assigned green spaces is minimized. We contribute a detailed presentation on how to engineer an assignment-based method such that it yields reasonable results (e.g., by considering distances in the road network) and becomes efficient enough for the analysis of large metropolitan areas (e.g., we were able to process an instance of Berlin with about 130000 polygons representing green spaces, 18000 polygons representing residential areas, and 6 million road segments). Furthermore, we show that the optimal assignments resulting from our method enable a subsequent analysis that reveals both interesting global properties of a city as well as spatial patterns. For example, our method allows us to identify neighborhoods with a shortage of green spaces, which will help spatial planners in their decision making.},
    author = {Niedermann, B. and Oehrlein, J. and Lautenbach, S. and Haunert, J.-H.},
    booktitle = {Proc. 10th International Conference on Geographic Information Science (GIScience '18)},
    doi = {10.4230/LIPIcs.GISCIENCE.2018.13},
    pages = {13:1--13:16},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {A network flow model for the analysis of green spaces in urban areas},
    volume = {114},
    year = {2018}
}

@inproceedings{nrw-eaorg-preprint-18,
    author = {Niedermann, B. and Rutter, I. and Wolf, M.},
    booktitle = {Proceedings of the 34rd European Workshop on Computational Geometry (EuroCG'18)},
    file = {nrw-eaorg-preprint-18.pdf:http\://i11www.ira.uka.de/extra/publications/nrw-eaorg-preprint-18.pdf:PDF},
    note = {Preprint.},
    title = {{Efficient Algorithms for Ortho-Radial Graph Drawing}},
    url = {https://conference.imp.fu-berlin.de/eurocg18/download/paper_71.pdf},
    year = {2018}
}

Finding a shortest path between two nodes in a graph is a well-studied problem whose applicability in practice crucially relies on the choice of the applied cost function. Especially, for the key application of vehicle routing the cost function may consist of more than one optimization criterion (e.g., distance, travel time, etc.). Finding a good balance between these criteria is a challenging and essential task. We present an approach that learns that balance from existing GPS-tracks. The core of our approach is to find a balance factor alpha for a given set of GPS-tracks such that the tracks can be decomposed into a minimum number of optimal paths with respect to alpha. In an experimental evaluation on real-world GPS-tracks of bicyclists we show that our approach yields an appropriate balance factor in a reasonable amount of time.

doi:10.1145/3139958.3140033

@inproceedings{Oehrlein:2017:IPW:3139958.3140033,
    abstract = {Finding a shortest path between two nodes in a graph is a well-studied problem whose applicability in practice crucially relies on the choice of the applied cost function. Especially, for the key application of vehicle routing the cost function may consist of more than one optimization criterion (e.g., distance, travel time, etc.). Finding a good balance between these criteria is a challenging and essential task. We present an approach that learns that balance from existing GPS-tracks. The core of our approach is to find a balance factor alpha for a given set of GPS-tracks such that the tracks can be decomposed into a minimum number of optimal paths with respect to alpha.

In an experimental evaluation on real-world GPS-tracks of bicyclists we show that our approach yields an appropriate balance factor in a reasonable amount of time.},
    author = {Oehrlein, J. and Niedermann, B. and Haunert, J.-H.},
    booktitle = {Proc. 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '17)},
    doi = {10.1145/3139958.3140033},
    pages = {59:1--59:4},
    title = {Inferring the Parametric Weight of a Bicriteria Routing Model from Trajectories},
    url = {http://doi.acm.org/10.1145/3139958.3140033},
    year = {2017}
}

@inproceedings{nnr-rclsl-17,
    author = {B. Niedermann and M. N{\"o}llenburg and I. Rutter},
    booktitle = {Proceedings of IEEE Pacific Visualization Symposium (PacificVis'17)},
    pages = {295--304},
    publisher = {IEEE Computer Society},
    title = {{Radial Contour Labeling with Straight Leaders}},
    year = {2017}
}

@inproceedings{nnr-rclsl-eurocg-17,
    author = {B. Niedermann and M. N{\"o}llenburg and I. Rutter},
    booktitle = {Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17)},
    note = {Preprint},
    title = {{Radial Contour Labeling with Straight Leaders}},
    url = {http://csconferences.mah.se/eurocg2017/proceedings.pdf},
    year = {2017}
}

@inproceedings{bnrw-ttsmf-17,
    author = {L. Barth and B. Niedermann and I. Rutter and M. Wolf},
    booktitle = {Proc. 33rd Annual ACM Symposium on Computational Geometry (SoCG '17)},
    pages = {14:1--14:16},
    series = {Leibniz International Proceedings in Informatics},
    title = {{Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings}},
    url = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2017.14},
    year = {2017}
}

@inproceedings{bnrw-ttsmf-preprint-17,
    author = {L. Barth and B. Niedermann and I. Rutter and M. Wolf},
    booktitle = {Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG'17)},
    file = {bnrw-ttsmf-preprint-17.pdf:http\://i11www.ira.uka.de/extra/publications/bnrw-ttsmf-preprint-17.pdf:PDF},
    note = {Preprint.},
    title = {{Towards a Topology-Shape-Metrics Framework for Ortho-Radial Drawings}},
    url = {http://csconferences.mah.se/eurocg2017/proceedings.pdf},
    year = {2017}
}

doi:10.5445/IR/1000068424

@phdthesis{Niedermann2017_1000068424,
    author = {B. Niedermann},
    doi = {10.5445/IR/1000068424},
    file = {1000068424:https\://publikationen.bibliothek.kit.edu/1000068424:PDF},
    keywords = {Label Placement, Labeling, Maps, Figures},
    language = {english},
    pagetotal = {285},
    publisher = {{Karlsruhe}},
    school = {Karlsruher Institut für Technologie (KIT)},
    series = {KIT-Bibiliothek},
    title = {Automatic Label Placement in Maps and Figures: Models, Algorithms and Experiments},
    type = {Dissertation},
    year = {2017}
}

@article{knrssw-msbl-16,
    author = {P. Kindermann and B. Niedermann and I. Rutter and M. Schaefer and A. Schulz and A. Wolff},
    journal = {Algorithmica},
    month = {September},
    number = {1},
    pages = {225--258},
    title = {Multi-Sided Boundary Labeling},
    url = {http://dx.doi.org/10.1007/s00453-015-0028-4},
    volume = {76},
    year = {2016}
}

@inproceedings{nn-aaflr-16,
    author = {Niedermann, B. and N{\"o}llenburg, M.},
    booktitle = {Proceedings of the 9th International Conference on Geographic Information Science (GIScience'16)},
    pages = {308--322},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{An Algorithmic Framework for Labeling Road Maps}},
    volume = {9927},
    year = {2016}
}

doi:10.1145/2996913.2996957

@inproceedings{bnns-tmlan-16,
    author = {L. Barth and B. Niedermann and M. N{\"o}llenburg and D. Strash},
    booktitle = {Proc. 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '16)},
    doi = {10.1145/2996913.2996957},
    pages = {23:1--23:10},
    publisher = {ACM},
    title = {{Temporal Map Labeling: A New Unified Framework with Experiments}},
    year = {2016}
}

@inproceedings{gnn-lprm-15,
    author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 9th Conference on Algorithms and Complexity (CIAC'15)},
    editor = {Peter Widmayer},
    file = {gnn-lprm-15.pdf:http\://i11www.ira.uka.de/extra/publications/gnn-lprm-15.pdf:PDF},
    note = {Full version available at http://arxiv.org/abs/1501.07188.},
    pages = {221--234},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Label Placement in Road Maps}},
    url = {http://dx.doi.org/10.1007/978-3-319-18173-8_16},
    volume = {9079},
    year = {2015}
}

@inproceedings{bgnn-orbl-15,
    author = {L. Barth and A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 23rd International Symposium on Graph Drawing (GD'15)},
    editor = {Di Giacomo, Emilio and Anna Lubiw},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{On the Readability of Boundary Labeling }},
    year = {2015}
}

@inproceedings{gnn-lprm-14,
    author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 30th European Workshop on Computational Geometry (EuroCG'14)},
    file = {gnn-lprm-14.pdf:http\://i11www.ira.uka.de/extra/publications/gnn-lprm-14.pdf:PDF},
    month = {March},
    note = {Preprint.},
    title = {{Label Placement in Road Maps}},
    year = {2014}
}

@inproceedings{bknn-pigra-14,
    author = {T. Bl{\"a}sius and F. Klute and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 22nd International Symposium on Graph Drawing (GD'14)},
    editor = {Christian A. Duncan and Antonios Symvonis},
    file = {bknn-pigra-14.pdf:http\://i11www.ira.uka.de/extra/publications/bknn-pigra-14.pdf:PDF},
    note = {Poster abstract.},
    pages = {513--514},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{PIGRA -- A Tool for Pixelated Graph Representations}},
    volume = {8871},
    year = {2014}
}

@inproceedings{gnn-tbdml-13,
    author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13)},
    title = {{Trajectory-Based Dynamic Map Labeling}},
    year = {2013}
}

@inproceedings{gnn-tbdml-isaac-13,
    author = {A. Gemsa and B. Niedermann and M. N{\"o}llenburg},
    booktitle = {Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC'13)},
    file = {gnn-tbdml-isaac-13.pdf:http\://i11www.ira.uka.de/extra/publications/gnn-tbdml-isaac-13.pdf:PDF},
    note = {Full version available at http://arxiv.org/abs/1309.3963.},
    pages = {413--423},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Trajectory-Based Dynamic Map Labeling}},
    url = {http://dx.doi.org/10.1007/978-3-642-45030-3_39},
    volume = {8283},
    year = {2013}
}

@inproceedings{knrssw-tsbla-13,
    author = {P. Kindermann and B. Niedermann and I. Rutter and M. Schaefer and A. Schulz and A. Wolff},
    booktitle = {Proceedings of the 29th European Workshop on Computational Geometry (EuroCG'13)},
    title = {{Two-Sided Boundary Labeling with Adjacent Sides}},
    year = {2013}
}

@inproceedings{knrss-tsbla-13,
    author = {P. Kindermann and B. Niedermann and I. Rutter and M. Schaefer and A. Schulz and A. Wolff},
    booktitle = {Algorithms and Data Structures, 13th International Symposium (WADS'13)},
    pages = {463--474},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Two-Sided Boundary Labeling with Adjacent Sides}},
    volume = {8037},
    year = {2013}
}

@inproceedings{bbnnpr-uilps-13,
    author = {T. Biedl and T. Bl{\"a}sius and B. Niedermann and M. N{\"o}llenburg and R. Prutkin and I. Rutter},
    booktitle = {Proceedings of the 21st International Symposium on Graph Drawing (GD'13)},
    editor = {Stephen K. Wismath and A. Wolff},
    file = {bbnnpr-uilps-13.pdf:http\://i11www.ira.uka.de/extra/publications/bbnnpr-uilps-13.pdf:PDF},
    note = {Full version available at http://arxiv.org/abs/1308.6778.},
    pages = {460--471},
    publisher = {Springer},
    series = {Lecture Notes in Computer Science},
    title = {{Using {ILP/SAT} to determine pathwidth, visibility representations, and other grid-based graph drawings}},
    url = {http://dx.doi.org/10.1007/978-3-319-03841-4_40},
    volume = {8242},
    year = {2013}
}