Many-to-One Boundary Labeling with Backbones

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BEKOS, Michael A., Sabine CORNELSEN, Martin FINK, Seok-Hee HONG, Michael KAUFMANN, Martin NÖLLENBURG, Ignaz RUTTER, Antonios SYMVONIS, 2015. Many-to-One Boundary Labeling with Backbones. In: Journal of Graph Algorithms and Applications. 19(3), pp. 779-816. eISSN 1526-1719. Available under: doi: 10.7155/jgaa.00379

@article{Bekos2015Manyt-44793, title={Many-to-One Boundary Labeling with Backbones}, year={2015}, doi={10.7155/jgaa.00379}, number={3}, volume={19}, journal={Journal of Graph Algorithms and Applications}, pages={779--816}, author={Bekos, Michael A. and Cornelsen, Sabine and Fink, Martin and Hong, Seok-Hee and Kaufmann, Michael and Nöllenburg, Martin and Rutter, Ignaz and Symvonis, Antonios} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:contributor>Nöllenburg, Martin</dc:contributor> <dspace:isPartOfCollection rdf:resource=""/> <dc:creator>Rutter, Ignaz</dc:creator> <dcterms:available rdf:datatype="">2019-01-31T13:50:08Z</dcterms:available> <dc:creator>Nöllenburg, Martin</dc:creator> <dcterms:title>Many-to-One Boundary Labeling with Backbones</dcterms:title> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Bekos, Michael A.</dc:contributor> <dc:creator>Bekos, Michael A.</dc:creator> <dcterms:abstract xml:lang="eng">We study a boundary labeling problem, where multiple points may connect to the same label. In this new many-to-one model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points that need to be connected to this label are linked via ver- tical line segments to the backbone. We present dynamic programming algorithms for minimizing the total number of label occurrences and for minimizing the total leader length of crossing-free backbone labelings. When crossings are allowed, we aim at obtaining solutions with the min- imum number of crossings. This can be achieved e ciently in the case of xed label order; however, in the case of exible label order we show that minimizing the number of leader crossings is NP-hard.</dcterms:abstract> <dcterms:issued>2015</dcterms:issued> <dc:creator>Hong, Seok-Hee</dc:creator> <dc:creator>Kaufmann, Michael</dc:creator> <dc:contributor>Kaufmann, Michael</dc:contributor> <dc:creator>Symvonis, Antonios</dc:creator> <bibo:uri rdf:resource=""/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Rutter, Ignaz</dc:contributor> <dcterms:isPartOf rdf:resource=""/> <dc:creator>Cornelsen, Sabine</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Fink, Martin</dc:contributor> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dc:creator>Fink, Martin</dc:creator> <dc:date rdf:datatype="">2019-01-31T13:50:08Z</dc:date> <dc:contributor>Symvonis, Antonios</dc:contributor> <dc:contributor>Hong, Seok-Hee</dc:contributor> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account