In point-set-embeddability (PSE) problems one is given not just a graph that is to be drawn, but also a set of points in the plane that specify where the vertices of the graph can be placed. The problem class was introduced by Gritzmann et al. [3] twenty years ago. In their work and most other works on PSE problems, however, planarity of the output drawing was an essential requirement. Recent experiments on the readability of drawings [4] showed that polyline drawings with angles at edge crossings close to 90 degrees. and a small number of bends per edge are just as readable as planar drawings. Motivated by these findings, Didimo et al. [2] recently introduced RAC drawings where pairs of crossing edges must form a right angle and, more generally, xAC drawings (for x in (0, 90]) where the crossing angle must be at least x. As usual, edges may not overlap and may not go through vertices. We investigate the intersection of PSE and RAC/xAC.

doi:10.1007/978-3-642-25878-7_43

@inproceedings{Fink2012,
    abstract = {In point-set-embeddability (PSE) problems one is given not just a graph that is to be drawn, but also a set of points in the plane that specify where the vertices of the graph can be placed. The problem class was introduced by Gritzmann et al. [3] twenty years ago. In their work and most other works on PSE problems, however, planarity of the output drawing was an essential requirement. Recent experiments on the readability of drawings [4] showed that polyline drawings with angles at edge crossings close to 90 degrees. and a small number of bends per edge are just as readable as planar drawings. Motivated by these findings, Didimo et al. [2] recently introduced RAC drawings where pairs of crossing edges must form a right angle and, more generally, xAC drawings (for x in (0, 90]) where the crossing angle must be at least x. As usual, edges may not overlap and may not go through vertices. We investigate the intersection of PSE and RAC/xAC.},
    author = {Fink, M. and Haunert, J.-H. and Mchedlidze, T. and Spoerhase, J. and Wolff, A.},
    booktitle = {Proc. Workshop on Algorithms and Computation (WALCOM'12)},
    doi = {10.1007/978-3-642-25878-7_43},
    pages = {186--197},
    publisher = {Springer-Verlag, Berlin, Germany},
    series = {Lecture Notes in Computer Science},
    timestamp = {2011-12-16T11:22:02.000+0100},
    title = {Drawing Graphs with Vertices at Specified Positions and Crossings at Large Angles},
    url = {http://www1.informatik.uni-wuerzburg.de/pub/wolff/pub/fhmsw-dgvsp-12.pdf},
    volume = {7157},
    year = {2012}
}

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. \par 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 straight-line 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. \par 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 facility-location 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.

doi:10.1109/TVCG.2012.193

@article{FinkEtAl2012,
    abstract = {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. \par 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 straight-line segments or B\'ezier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics. \par 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 facility-location 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.},
    author = {Fink, M. and Haunert, J.-H. and Schulz, A. and Spoerhase, J. and Wolff, A.},
    doi = {10.1109/TVCG.2012.193},
    file = {fhssw-alfr-InfoVis12.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/fink/paper/fhssw-alfr-InfoVis12.pdf:PDF},
    journal = {IEEE Transactions on Visualization and Computer Graphics},
    number = {12},
    pages = {2583--2592},
    timestamp = {2013-03-13T10:23:34.000+0100},
    title = {Algorithms for Labeling Focus Regions},
    volume = {18},
    year = {2012}
}

This article presents an algorithmic approach to the problem of finding symmetries in building footprints, which is motivated by map generalization tasks such as symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in vector data that use algorithms for string matching. It detects both mirror symmetries and repetitions of geometric structures. In addition to the existing vector-based methods, the new method finds partial symmetries in polygons while allowing for small geometric errors and, based on a least-squares approach, computes optimally adjusted mirror axes and assesses their quality. Finally, the problem of grouping symmetry relations is addressed with an algorithm that finds mirror axes that are almost collinear. The presented approach was tested on a large building dataset of the metropolitan Boston area and its results were compared with results that were manually generated in an empirical test. The symmetry relations that the participants of the test considered most important were found by the algorithm. Future work will deal with the integration of information on symmetry relations into algorithms for map generalization.

doi:10.1016/j.isprsjprs.2012.08.004

@article{Haunert2012,
    abstract = {This article presents an algorithmic approach to the problem of finding symmetries in building footprints, which is motivated by map generalization tasks such as symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in vector data that use algorithms for string matching. It detects both mirror symmetries and repetitions of geometric structures. In addition to the existing vector-based methods, the new method finds partial symmetries in polygons while allowing for small geometric errors and, based on a least-squares approach, computes optimally adjusted mirror axes and assesses their quality. Finally, the problem of grouping symmetry relations is addressed with an algorithm that finds mirror axes that are almost collinear. The presented approach was tested on a large building dataset of the metropolitan Boston area and its results were compared with results that were manually generated in an empirical test. The symmetry relations that the participants of the test considered most important were found by the algorithm. Future work will deal with the integration of information on symmetry relations into algorithms for map generalization.},
    author = {Haunert, J.-H.},
    doi = {10.1016/j.isprsjprs.2012.08.004},
    file = {HaunertISPRS2012.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertISPRS2012.pdf:PDF},
    journal = {ISPRS Journal of Photogrammetry and Remote Sensing},
    pages = {66--77},
    timestamp = {2013-03-13T10:45:41.000+0100},
    title = {A Symmetry Detector for Map Generalization and Urban-Space Analysis},
    volume = {74},
    year = {2012}
}

We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336-343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.

@inproceedings{HaunertBudig2012,
    abstract = {We consider the problem of matching a GPS trajectory with a road data set in which some roads are missing. To solve this problem, we extend a map-matching algorithm by Newson and Krumm (Proc. ACM GIS 2009, pp. 336--343) that is based on a hidden Markov model and a discrete set of candidate matches for each point of the trajectory. We introduce an additional off-road candidate for each point of the trajectory. The output path becomes determined by selecting one candidate for each point of the trajectory and connecting the selected candidates via shortest paths, which preferably lie in the road network but, if off-road candidates become selected, may also include off-road sections. We discuss experiments with GPS tracks of pedestrians.},
    author = {Haunert, J.-H. and Budig, B.},
    booktitle = {Proc. 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '12)},
    file = {HaunertBudig2012.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertBudig2012.pdf:PDF},
    pages = {510--513},
    timestamp = {2013-03-13T10:45:54.000+0100},
    title = {An algorithm for map matching given incomplete road data},
    url = {http://dl.acm.org/citation.cfm?doid=2424321.2424402},
    year = {2012}
}